이진 검색 트리 2

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

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

이진 검색 트리 $T$에서 키 $k$를 찾을 때는 루트에서 시작한다. $T$가 비어 있으면 검색은 실패한다. 그렇지 않으면 루트의 키와 $k$를 비교한다. $k$가 루트의 키와 같으면 검색은 성공한다. $k$가 루트의 키보다 작으면 왼쪽 서브트리에서, 크면 오른쪽 서브트리에서 같은 방법으로 검색을 이어간다.

트리에 없는 새로운 키 $k$를 삽입할 때는 먼저 $k$를 검색한다. $k$가 트리에 없으므로 검색은 반드시 실패하는데, 검색이 실패로 끝난 그 빈 자리에 $k$를 새 노드로 붙인다.

이 문제에서는 키가 $1, 2, \dots, N$인 이진 검색 트리를 다룬다. $\{1, 2, \dots, N\}$의 순열 $a_1, a_2, \dots, a_N$을 앞에서부터 차례대로 비어 있는 트리에 삽입하면 하나의 이진 검색 트리가 만들어진다. 서로 다른 순열이 같은 모양의 트리를 만들 수도 있다.

예를 들어 순열 2 1 4 3 5를 삽입하면 다음과 같은 트리가 만들어진다.

    2
   / \
  1   4
     / \
    3   5

순열 2 4 3 1 5도 같은 트리를 만든다. $\{1, 2, 3, 4, 5\}$의 순열 중에서 이 트리와 똑같은 트리를 만드는 순열은 모두 8개이다.

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

첫째 줄에 테스트 케이스의 개수 $T$ ($T \le 100$)가 주어진다. 각 테스트 케이스의 첫째 줄에는 키의 개수 $N$ ($1 \le N \le 20$)이 주어지고, 둘째 줄에는 길이가 $N$인 $\{1, 2, \dots, N\}$의 순열이 주어진다.

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