트리 삽입 순열 세기

현대의 모든 은행은 정보 시스템을 이용해 데이터를 처리합니다. 처리해야 하는 데이터의 양은 엄청나게 많습니다. 수많은 거래, 결제, 인터넷 뱅킹, 웹 서비스 등을 떠올려 보세요. 따라서 데이터를 저장하고 매우 빠르게 접근하려면 정교한 자료구조가 필요합니다.

이진 탐색 트리(Binary Search Tree, BST)는 그러한 자료구조의 한 예입니다. BST는 값들의 모음을 담으며, 이 값들 사이에는 선형 순서를 부여하는 비교 연산이 정의되어 있습니다.

BST는 노드들로 이루어지며, 각 노드는 하나의 값을 담고 최대 두 개의 자식 노드(왼쪽, 오른쪽)를 가집니다(즉 BST는 이진 트리입니다). 왼쪽 서브트리에는 항상 노드의 값보다 엄격히 작은 값만, 오른쪽 서브트리에는 노드의 값보다 크거나 같은 값만 들어갑니다.

이 덕분에 트리를 재귀적으로 순회하며 값을 쉽게 찾을 수 있습니다. 루트 노드에서 시작해 찾으려는 값과 노드의 값을 비교하고, 결과에 따라 왼쪽 또는 오른쪽 서브트리로 내려갑니다. 양쪽을 모두 살펴볼 필요는 결코 없습니다.

이미 존재하는 트리에 값을 삽입하는 절차도 간단합니다. (트리가 비어 있을 때) 첫 번째 값은 항상 루트가 됩니다. 트리가 이미 있다면 탐색과 마찬가지로 루트에서 시작해 재귀적으로 순회합니다. 순회하다가 자식 노드가 없는 자리에 도달하면, 그 자리에 새 리프 노드를 만들어 새 값을 넣습니다.

아래 그림은 다음 수열을 차례대로 삽입했을 때 만들어지는 트리를 보여 줍니다: 3, 4, 3, 5, 4, 1, 2.

같은 수들이라도 서로 다른 순열로 삽입하면 종종 같은 BST가 만들어진다는 점을 알 수 있습니다. 예를 들어 위 다섯 번째 그림의 트리는 다음 세 가지 서로 다른 입력 수열로 만들 수 있습니다.

• 3, 4, 3, 5, 4
• 3, 4, 5, 4, 3
• 3, 4, 5, 3, 4

여러분의 과제는, 같은 BST를 만들어 내는 서로 다른 순열이 몇 개인지 세는 것입니다.

입력은 여러 개의 트리로 이루어집니다. 각 트리는 두 줄로 주어집니다. 첫째 줄에는 트리에 들어가는 값의 개수인 정수 $N$ ($1 \le N \le 100$)이 주어집니다. 둘째 줄에는 공백으로 구분된 $N$개의 값이 주어집니다. 이 값들을 주어진 순서대로 삽입하면 우리가 살펴볼 BST가 만들어집니다. 모든 값은 $0$ 이상 $1000$ 이하입니다.

마지막 트리 다음에는 정수 $0$ 하나만 있는 줄이 옵니다.

각 트리에 대해, 같은 이진 탐색 트리를 만들어 내는 서로 다른 순열의 총 개수를 한 줄에 하나씩 출력하세요. 이 값은 $2^{32}$을 넘을 수 있으므로 임의 정밀도(큰 수) 정수 연산을 사용해야 합니다.