Binary Search Tree

A binary search tree is a binary tree, and it may be empty. A non-empty binary search tree satisfies the following properties.

1. Every node holds a distinct key.
2. Every key in the left subtree of a node is smaller than that node's key.
3. Every key in the right subtree of a node is larger than that node's key.
4. The left subtree and the right subtree are themselves binary search trees.

Searching for a key $k$ in a binary search tree $T$ works as follows. Start at the root; if $T$ is empty, the search fails. Otherwise, compare $k$ with the root's key. If they are equal, the search succeeds. If $k$ is smaller than the root's key, continue in the left subtree; if it is larger, continue in the right subtree.

To insert a new key $k$ that is not already in $T$, first search for $k$ in $T$. Since $k$ is not present, the search fails, and $k$ is inserted as a new node at the empty spot where the search stopped.

In this problem we work with binary search trees whose keys are $1, 2, \dots, N$. Given a permutation $a_1, a_2, \dots, a_N$ of $\{1, 2, \dots, N\}$, inserting $a_1$ through $a_N$ in order into an empty tree produces one binary search tree.

Different permutations may produce the same tree. For example, inserting the permutation $2\ 1\ 4\ 3\ 5$ in order builds the tree whose root is $2$ with left child $1$ and right child $4$, where $4$ has left child $3$ and right child $5$. The permutation $2\ 4\ 3\ 1\ 5$ builds exactly the same tree. Among all permutations of $\{1, 2, 3, 4, 5\}$, there are $8$ that build this tree.

Given $N$ and a permutation $P$, write a program that counts how many permutations build the same binary search tree as $P$.

The first line contains the number of test cases $T$ ($T \le 40{,}320$).

Each test case consists of two lines. The first line contains the number of keys $N$ ($1 \le N \le 20$), and the second line contains a permutation of $\{1, 2, \dots, N\}$ of length $N$, separated by spaces.

For each test case, print on its own line the number of permutations that build the same binary search tree as the given permutation, modulo $9{,}999{,}991$.