시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 106 39 23 32.857%

문제

이진 검색 트리는 이진 트리이다. 트리는 비어있을 수도 있다. 비어있지 않은 경우에는 다음과 같은 특징을 가진다.

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

아래 그림은 이진 검색 트리의 예이다.

이진 검색 트리 T에서 k가 키인 노드를 찾으려면, 먼저 루트에서 시작해야 한다. T가 비어있다면, T는 키를 가지고 있지 않기 때문에 검색은 실패한다. 비어있지 않은 경우에는 루트의 키와 k를 비교한다. 만약, k가 루트의 키와 같다면, 검색은 성공적으로 종료된다. k가 루트의 키보다 작은 경우에는 왼쪽 서브트리의 루트에서 검색을 시작한다. k가 루트의 키보드 큰 경우에는 오른쪽 서브 트리의 루트에서 검색을 시작한다. 같은 과정으로 T의 왼쪽 또는 오른쪽 서브 트리에서 검색을 수행한다.

이진 검색 트리 T에 T에 존재하지 않는 새로운 키 k를 삽입하려면, 먼저 T에서 k를 찾아야 한다. T에는 k가 없기 때문에, 검색은 실패로 끝날 것이고, 실패로 끝난 그 위치에 새로운 키 k를 삽입한다. 예를 들어, 위의 그림 (a)에 80을 삽입하는 경우를 살펴보자. 먼저, 트리에서 80을 찾아야 한다. 검색은 실패로 끝나고, 마지막으로 검사한 키는 40이다. 80을 그 노드의 오른쪽 자식으로 삽입하면, 이진 검색트리는 (b)와 같아진다.

이 문제에서는 1, 2, ..., N 총 N개의 키를 가지고 있는 이진 검색 트리를 이용한다. {1, 2, ..., N}의 순열 a1, a2, ..., aN에 대해서, a1, a2, ..., aN을 순서대로 비어있는 이진 검색 트리에 삽입한다면, 이진 검색 트리를 만들 수 있다. 예를 들어, 순열 2 1 4 3 5는 그림 (c)를 만들 수 있다. 또, 2 4 3 1 5도 같은 트리를 만든다. {1, 2, 3, 4, 5}의 순열 중에서 그림 (c)와 같은 이진 검색 트리를 만드는 순열의 개수는 8개이다.

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

입력

첫째 줄에 테스트 케이스의 개수 T (≤ 40,320)가 주어진다. 각 테스트 케이스의 첫째 줄에는 키의 수 N이 주어진다. (1 ≤ N ≤ 20) 다음 줄에는 길이가 N인 순열이 주어진다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 순열과 같은 트리를 만드는 순열의 개수를 9,999,991로 나눈 나머지를 출력한다.

예제 입력

3
5
2 1 4 3 5
4
2 4 1 3
12
1 2 3 4 5 6 7 8 9 10 11 12

예제 출력

8
3
1

힌트

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2010 E번