You are given N nodes, each having unique value ranging from [1, N], how many different binary search tree can be created using all of them.

Input
First line will contain an integer, T, number of test cases. Then T lines follow, where each line represent a test case. Each test case consists a single integer, N, where N is the number of nodes in the binary search tree.

Output
For each test case, find the number of different binary search trees that can be created using these nodes. Print the answer modulo (108+7).

Constraints
1 <= T <= 1000
1 <= N <= 1000

Sample Input
5
1
2
3
4
100

Sample Output
1
2
5
14
25666077

So you want to find the max number of BTS trees with a given node count. This shouldn't be done by making all the trees, that would be a huge amount of trees so I did some research and found that you can use the formula shown in the image below. In order to not have to do a large series of Factorials that will not be used again I made sure to build the entire set of Factorials for all numbers 1 to 2000, as the max number of N is 1000 and Catalan numbers need 2N

    def map_factorial(limit \\ 2000) do
      Enum.reduce(1..limit, %{0 => 1}, fn index, acc ->
        Map.put(acc, index, acc[index - 1] * index)
      end)
    end
  
    def find_factorial(number, factorials) do
      {:ok, number} = Map.fetch(factorials, number)
      number
    end

As you can see I make sure to set a map with all the Factorials with their starting number as the key, and then we make sure to use a find factorial for finding the factorial in the map. 

    defp catalan_number(n, factorials) do
      div(
        find_factorial(2 * n, factorials),
        find_factorial(n + 1, factorials) * find_factorial(n, factorials)
      )
    end

Lastly we use the div and find_factorial to quickly lookup the factorial and then compute the Catalan number.