Ways to a BST
Problem
You are given N distinct numbers in the form of an array Arri. You can form a Binary Search Tree(BST) by inserting them in the order they are given.Now find the number of different permutations of the array, so that the BST formed in each permutation is same as that of the given array(including the given permutation). As the number can be large, output modulo (109+7).
Constraints:
- 1≤T≤10
- 1≤N≤1000
- 1≤Arri≤1000000000
Format of the input file:
First line : T i.e Number of testcases.
For each testcase :
First line : N.
Second line : N space separated integers denoting the array .
Format of the output file:
Output the answer to each testcase in a separate line.
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
All possible arrangements of the given array are :-
{4 2 5 6 3}
{4 2 5 3 6}
{4 2 3 5 6}
{4 5 6 2 3}
{4 5 2 6 3}
