이진 검색 트리

이진 검색 트리는 이진 트리이며, 비어 있을 수도 있다. 비어 있지 않은 이진 검색 트리는 다음 성질을 만족한다.

1. 모든 노드는 서로 다른 키를 가진다.
2. 어떤 노드의 왼쪽 서브 트리에 있는 모든 키는 그 노드의 키보다 작다.
3. 어떤 노드의 오른쪽 서브 트리에 있는 모든 키는 그 노드의 키보다 크다.
4. 왼쪽 서브 트리와 오른쪽 서브 트리도 각각 이진 검색 트리이다.

이진 검색 트리 $T$에서 키 $k$를 찾는 과정은 다음과 같다. 루트에서 시작하며, $T$가 비어 있으면 검색은 실패한다. 비어 있지 않으면 루트의 키와 $k$를 비교한다. 두 값이 같으면 검색은 성공으로 끝난다. $k$가 루트의 키보다 작으면 왼쪽 서브 트리에서, 크면 오른쪽 서브 트리에서 같은 과정을 반복한다.

$T$에 존재하지 않는 새로운 키 $k$를 삽입할 때는, 먼저 $T$에서 $k$를 찾는다. $k$는 트리에 없으므로 검색은 실패로 끝나고, 검색이 멈춘 그 빈 자리에 $k$를 새 노드로 삽입한다.

이 문제에서는 키가 $1, 2, \dots, N$인 이진 검색 트리를 다룬다. $\{1, 2, \dots, N\}$의 순열 $a_1, a_2, \dots, a_N$이 주어지면, 비어 있는 트리에 $a_1$부터 $a_N$까지 순서대로 삽입하여 하나의 이진 검색 트리를 만들 수 있다.

서로 다른 순열이 같은 트리를 만들 수도 있다. 예를 들어 순열 $2\ 1\ 4\ 3\ 5$를 차례대로 삽입하면, 루트가 $2$이고 그 왼쪽 자식이 $1$, 오른쪽 자식이 $4$이며, $4$의 왼쪽 자식이 $3$, 오른쪽 자식이 $5$인 트리가 만들어진다. 순열 $2\ 4\ 3\ 1\ 5$도 정확히 같은 트리를 만든다. $\{1, 2, 3, 4, 5\}$의 순열 중 이 트리와 같은 트리를 만드는 순열은 모두 $8$개이다.

$N$과 순열 $P$가 주어졌을 때, $P$와 같은 이진 검색 트리를 만드는 순열의 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($T \le 40{,}320$)

각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에 키의 개수 $N$이 주어지고 ($1 \le N \le 20$), 둘째 줄에 길이가 $N$인 $\{1, 2, \dots, N\}$의 순열이 공백으로 구분되어 주어진다.

각 테스트 케이스마다, 입력으로 주어진 순열과 같은 이진 검색 트리를 만드는 순열의 개수를 $9{,}999{,}991$로 나눈 나머지를 한 줄에 하나씩 출력한다.