시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 187 69 49 35.252%

문제

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

  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로 나눈 나머지를 출력한다.

예제 입력 1

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

예제 출력 1

8
3
1
W3sicHJvYmxlbV9pZCI6Ijg5MTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NzRcdWM5YzQgXHVhYzgwXHVjMGM5IFx1ZDJiOFx1YjlhYyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNzc0XHVjOWM0IFx1YWM4MFx1YzBjOSBcdWQyYjhcdWI5YWNcdWIyOTQgXHVjNzc0XHVjOWM0IFx1ZDJiOFx1YjlhY1x1Yzc3NFx1YjJlNC4gXHVkMmI4XHViOWFjXHViMjk0IFx1YmU0NFx1YzViNFx1Yzc4OFx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWJlNDRcdWM1YjRcdWM3ODhcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1ZDJiOVx1YzlkNVx1Yzc0NCBcdWFjMDBcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHViYWE4XHViNGUwIFx1YjE3OFx1YjRkY1x1YjI5NCBcdWQwYTRcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViNDUwIFx1YjE3OFx1YjRkY1x1YWMwMCBcdWFjMTlcdWM3NDAgXHVkMGE0XHViOTdjIFx1YWMwMFx1YzljOCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWJlNDRcdWM1YjRcdWM3ODhcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YzY3Y1x1Y2FiZCBcdWMxMWNcdWJlMGMgXHVkMmI4XHViOWFjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVkMGE0XHViMjk0IFx1YWRmOCBcdWMxMWNcdWJlMGMgXHVkMmI4XHViOWFjXHVjNzU4IFx1YjhlOFx1ZDJiOFx1Yzc1OCBcdWQwYTRcdWJjZjRcdWIyZTQgXHVjNzkxXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWJlNDRcdWM1YjRcdWM3ODhcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWMxMWNcdWJlMGMgXHVkMmI4XHViOWFjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVkMGE0XHViMjk0IFx1YWRmOCBcdWMxMWNcdWJlMGMgXHVkMmI4XHViOWFjXHVjNzU4IFx1YjhlOFx1ZDJiOFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVkMGE0XHViY2Y0XHViMmU0IFx1ZDA2Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNjdjXHVjYWJkIFx1YzExY1x1YmUwYyBcdWQyYjhcdWI5YWNcdWM2NDAgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzExY1x1YmUwYyBcdWQyYjhcdWI5YWNcdWIzYzQgXHVjNzc0XHVjOWM0IFx1YWM4MFx1YzBjOSBcdWQyYjhcdWI5YWNcdWM3NzRcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWM3NzRcdWM5YzQgXHVhYzgwXHVjMGM5IFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWM2MDhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdHJlZXBlcm0ucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjI0cHg7IHdpZHRoOjUyNnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YzljNCBcdWFjODBcdWMwYzkgXHVkMmI4XHViOWFjIFRcdWM1ZDBcdWMxMWMga1x1YWMwMCBcdWQwYTRcdWM3NzggXHViMTc4XHViNGRjXHViOTdjIFx1Y2MzZVx1YzczY1x1YjgyNFx1YmE3NCwgXHViYTNjXHVjODAwIFx1YjhlOFx1ZDJiOFx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBUXHVhYzAwIFx1YmU0NFx1YzViNFx1Yzc4OFx1YjJlNFx1YmE3NCwgVFx1YjI5NCBcdWQwYTRcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YzljMCBcdWM1NGFcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YWM4MFx1YzBjOVx1Yzc0MCBcdWMyZTRcdWQzMjhcdWQ1NWNcdWIyZTQuIFx1YmU0NFx1YzViNFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YjhlOFx1ZDJiOFx1Yzc1OCBcdWQwYTRcdWM2NDAga1x1Yjk3YyBcdWJlNDRcdWFkNTBcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwga1x1YWMwMCBcdWI4ZThcdWQyYjhcdWM3NTggXHVkMGE0XHVjNjQwIFx1YWMxOVx1YjJlNFx1YmE3NCwgXHVhYzgwXHVjMGM5XHVjNzQwIFx1YzEzMVx1YWNmNVx1YzgwMVx1YzczY1x1Yjg1YyBcdWM4ODVcdWI4Y2NcdWI0MWNcdWIyZTQuIGtcdWFjMDAgXHViOGU4XHVkMmI4XHVjNzU4IFx1ZDBhNFx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzY3Y1x1Y2FiZCBcdWMxMWNcdWJlMGNcdWQyYjhcdWI5YWNcdWM3NTggXHViOGU4XHVkMmI4XHVjNWQwXHVjMTFjIFx1YWM4MFx1YzBjOVx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIGtcdWFjMDAgXHViOGU4XHVkMmI4XHVjNzU4IFx1ZDBhNFx1YmNmNFx1YjRkYyBcdWQwNzAgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWMxMWNcdWJlMGMgXHVkMmI4XHViOWFjXHVjNzU4IFx1YjhlOFx1ZDJiOFx1YzVkMFx1YzExYyBcdWFjODBcdWMwYzlcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWFjMTlcdWM3NDAgXHVhY2ZjXHVjODE1XHVjNzNjXHViODVjIFRcdWM3NTggXHVjNjdjXHVjYWJkIFx1YjYxMFx1YjI5NCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjMTFjXHViZTBjIFx1ZDJiOFx1YjlhY1x1YzVkMFx1YzExYyBcdWFjODBcdWMwYzlcdWM3NDQgXHVjMjE4XHVkNTg5XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM5YzQgXHVhYzgwXHVjMGM5IFx1ZDJiOFx1YjlhYyBUXHVjNWQwIFRcdWM1ZDAgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVkMGE0IGtcdWI5N2MgXHVjMGJkXHVjNzg1XHVkNTU4XHViODI0XHViYTc0LCBcdWJhM2NcdWM4MDAgVFx1YzVkMFx1YzExYyBrXHViOTdjIFx1Y2MzZVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFRcdWM1ZDBcdWIyOTQga1x1YWMwMCBcdWM1YzZcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWFjODBcdWMwYzlcdWM3NDAgXHVjMmU0XHVkMzI4XHViODVjIFx1YjA1ZFx1YjBhMCBcdWFjODNcdWM3NzRcdWFjZTAsIFx1YzJlNFx1ZDMyOFx1Yjg1YyBcdWIwNWRcdWIwOWMgXHVhZGY4IFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVkMGE0IGtcdWI5N2MgXHVjMGJkXHVjNzg1XHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWM3MDRcdWM3NTggXHVhZGY4XHViOWJjIChhKVx1YzVkMCA4MFx1Yzc0NCBcdWMwYmRcdWM3ODVcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHViOTdjIFx1YzBiNFx1ZDNiNFx1YmNmNFx1Yzc5MC4gXHViYTNjXHVjODAwLCBcdWQyYjhcdWI5YWNcdWM1ZDBcdWMxMWMgODBcdWM3NDQgXHVjYzNlXHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVhYzgwXHVjMGM5XHVjNzQwIFx1YzJlNFx1ZDMyOFx1Yjg1YyBcdWIwNWRcdWIwOThcdWFjZTAsIFx1YjljOFx1YzljMFx1YjljOVx1YzczY1x1Yjg1YyBcdWFjODBcdWMwYWNcdWQ1NWMgXHVkMGE0XHViMjk0IDQwXHVjNzc0XHViMmU0LiA4MFx1Yzc0NCBcdWFkZjggXHViMTc4XHViNGRjXHVjNzU4IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM3OTBcdWMyZGRcdWM3M2NcdWI4NWMgXHVjMGJkXHVjNzg1XHVkNTU4XHViYTc0LCBcdWM3NzRcdWM5YzQgXHVhYzgwXHVjMGM5XHVkMmI4XHViOWFjXHViMjk0IChiKVx1YzY0MCBcdWFjMTlcdWM1NDRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWNcdWIyOTQgMSwgMiwgLi4uLCBOIFx1Y2QxZCBOXHVhYzFjXHVjNzU4IFx1ZDBhNFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0IFx1Yzc3NFx1YzljNCBcdWFjODBcdWMwYzkgXHVkMmI4XHViOWFjXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU1Y1x1YjJlNC4gezEsIDIsIC4uLiwgTn1cdWM3NTggXHVjMjFjXHVjNWY0IGE8c3ViPjE8XC9zdWI+LCBhPHN1Yj4yPFwvc3ViPiwgLi4uLCBhPHN1Yj5OPFwvc3ViPlx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIGE8c3ViPjE8XC9zdWI+LCBhPHN1Yj4yPFwvc3ViPiwgLi4uLCBhPHN1Yj5OPFwvc3ViPlx1Yzc0NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViZTQ0XHVjNWI0XHVjNzg4XHViMjk0IFx1Yzc3NFx1YzljNCBcdWFjODBcdWMwYzkgXHVkMmI4XHViOWFjXHVjNWQwIFx1YzBiZFx1Yzc4NVx1ZDU1Y1x1YjJlNFx1YmE3NCwgXHVjNzc0XHVjOWM0IFx1YWM4MFx1YzBjOSBcdWQyYjhcdWI5YWNcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzIxY1x1YzVmNCAyIDEgNCAzIDVcdWIyOTQgXHVhZGY4XHViOWJjIChjKVx1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNjEwLCAyIDQgMyAxIDVcdWIzYzQgXHVhYzE5XHVjNzQwIFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWI5Y2NcdWI0ZTBcdWIyZTQuIHsxLCAyLCAzLCA0LCA1fVx1Yzc1OCBcdWMyMWNcdWM1ZjQgXHVjOTExXHVjNWQwXHVjMTFjIFx1YWRmOFx1YjliYyAoYylcdWM2NDAgXHVhYzE5XHVjNzQwIFx1Yzc3NFx1YzljNCBcdWFjODBcdWMwYzkgXHVkMmI4XHViOWFjXHViOTdjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWMyMWNcdWM1ZjRcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IDhcdWFjMWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk5cdWFjZmMgXHVjMjFjXHVjNWY0IFBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhZGY4IFx1YzIxY1x1YzVmNFx1YWNmYyBcdWFjMTlcdWM3NDAgXHVjNzc0XHVjOWM0IFx1YWM4MFx1YzBjOSBcdWQyYjhcdWI5YWNcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1YzIxY1x1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQgKCZsZTsgNDAsMzIwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMGE0XHVjNzU4IFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMjApIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZTM4XHVjNzc0XHVhYzAwIE5cdWM3NzggXHVjMjFjXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMjFjXHVjNWY0XHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWQyYjhcdWI5YWNcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1YzIxY1x1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgOSw5OTksOTkxXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijg5MTYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCaW5hcnkgU2VhcmNoIFRyZWUiLCJkZXNjcmlwdGlvbiI6IjxwPkEgYmluYXJ5IHNlYXJjaCB0cmVlIGlzIGEgYmluYXJ5IHRyZWUuIEl0IG1heSBiZSBlbXB0eS4gSWYgaXQgaXMgbm90IGVtcHR5LCBpdCBzYXRpc2ZpZXMgdGhlIGZvbGxvd2luZyBwcm9wZXJ0aWVzOjxcL3A+XHJcblxyXG48cD5FdmVyeSBub2RlIGhhcyBhIGtleSwgYW5kIG5vIHR3byBub2RlcyBoYXZlIHRoZSBzYW1lIGtleS48YnIgXC8+XHJcblRoZSBrZXlzIGluIGEgbm9uZW1wdHkgbGVmdCBzdWJ0cmVlIG11c3QgYmUgc21hbGxlciB0aGFuIHRoZSBrZXkgaW4gdGhlIHJvb3Qgb2YgdGhlIHN1YnRyZWUuPGJyIFwvPlxyXG5UaGUga2V5cyBpbiBhIG5vbmVtcHR5IHJpZ2h0IHN1YnRyZWUgbXVzdCBiZSBsYXJnZXIgdGhhbiB0aGUga2V5IGluIHRoZSByb290IG9mIHRoZSBzdWJ0cmVlLjxiciBcLz5cclxuVGhlIGxlZnQgYW5kIHJpZ2h0IHN1YnRyZWVzIGFyZSBhbHNvIGJpbmFyeSBzZWFyY2ggdHJlZXMuPFwvcD5cclxuXHJcbjxwPlNhbXBsZSBiaW5hcnkgc2VhcmNoIHRyZWVzIGFyZSBzaG93biBpbiBGaWd1cmUgMS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90cmVlcGVybS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMjRweDsgd2lkdGg6NTI2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDEuIGJpbmFyeSBzZWFyY2ggdHJlZXM8XC9wPlxyXG5cclxuPHA+VG8gc2VhcmNoIGZvciBhIG5vZGUgd2l0aCBhIGtleSBrIGluIGEgYmluYXJ5IHNlYXJjaCB0cmVlIFQgLCB3ZSBiZWdpbiBhdCB0aGUgcm9vdC4gSWYgVCBpcyBlbXB0eSwgVCBjb250YWlucyBubyBrZXlzIGFuZCB0aGUgc2VhcmNoIGlzIHVuc3VjY2Vzc2Z1bC4gT3RoZXJ3aXNlLCB3ZSBjb21wYXJlIGsgd2l0aCB0aGUga2V5IGluIHJvb3QuIElmIGsgZXF1YWxzIHJvb3QmcnNxdW87cyBrZXksIHRoZW4gdGhlIHNlYXJjaCB0ZXJtaW5hdGVzIHN1Y2Nlc3NmdWxseS4gSWYgayBpcyBsZXNzIHRoYW4gcm9vdCZyc3F1bztzIGtleSwgd2Ugc2VhcmNoIHRoZSBsZWZ0IHN1YnRyZWUgb2YgdGhlIHJvb3QuIElmIGtpcyBsYXJnZXIgdGhhbiByb290JnJzcXVvO3Mga2V5LCB3ZSBzZWFyY2ggdGhlIHJpZ2h0IHN1YnRyZWUgb2YgdGhlIHJvb3QuIEluIHRoZSBzYW1lIHdheSwgd2UgY2FuIHByb2NlZWQgdGhlIHNlYXJjaCBpbiB0aGUgbGVmdCBvciByaWdodCBzdWJyZWUgb2YgVCAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRvIGluc2VydCBhIG5ldyBrZXkgayBpbnRvIGEgYmluYXJ5IHNlYXJjaCB0cmVlIFQgd2hlcmUgayBpcyBkaWZmZXJlbnQgZnJvbSB0aG9zZSBvZiBleGlzdGluZyBrZXlzIGluIFQgLCB3ZSBmaXJzdCBzZWFyY2ggdGhlIHRyZWUgVCAuIFRoZSBzZWFyY2ggd2lsbCBiZSB1bnN1Y2Nlc3NmdWwsIHRoZW4gd2UgaW5zZXJ0IHRoZSBrZXkgYXQgdGhlIHBvaW50IHRoZSBzZWFyY2ggdGVybWluYXRlZC4gRm9yIGluc3RhbmNlLCB0byBpbnNlcnQgYSBrZXkgODAgaW50byB0aGUgRmlndXJlIDEoYSksIHdlIGZpcnN0IHNlYXJjaCB0aGUgdHJlZSBmb3IgODAuIFRoaXMgc2VhcmNoIHRlcm1pbmF0ZXMgdW5zdWNjZXNzZnVsbHksIGFuZCB0aGUgbGFzdCBub2RlIGV4YW1pbmVkIGhhcyBrZXkgNDAuIFdlIGluc2VydCBhIG5ldyBub2RlIGNvbnRhaW5pbmcgODAgYXMgdGhlIHJpZ2h0IGNoaWxkIG9mIHRoZSBub2RlLiBUaGUgcmVzdWx0aW5nIHNlYXJjaCB0cmVlIGlzIHNob3duIGluIEZpZ3VyZSAxKGIpLjxcL3A+XHJcblxyXG48cD5JbiB0aGlzIHByb2JsZW0sIHdlIGNvbnNpZGVyIGJpbmFyeSBzZWFyY2ggdHJlZXMgd2l0aCBOIGtleXMgMSwgMiwgLi4uICwgTiAuIEZvciBhIHBlcm11dGF0aW9uIGE8c3ViPjE8XC9zdWI+IGE8c3ViPjI8XC9zdWI+IC4uLiBhPHN1Yj5OPFwvc3ViPiBvZiB7MSwgMiwgLi4uICwgTiB9LCBpbnNlcnRpbmcgYTxzdWI+MTxcL3N1Yj4gYTxzdWI+MjxcL3N1Yj4gLi4uIGE8c3ViPk48XC9zdWI+IHN1Y2Nlc3NpdmVseSBpbnRvIGFuIGluaXRpYWxseSBlbXB0eSBiaW5hcnkgc2VhcmNoIHRyZWUgd2lsbCBwcm9kdWNlIGEgYmluYXJ5IHNlYXJjaCB0cmVlLiBGb3IgaW5zdGFuY2UsIHRoZSBwZXJtdXRhdGlvbiAyIDEgNCAzIDUgd2lsbCBwcm9kdWNlIHRoZSB0cmVlIGluIEZpZ3VyZSAxKGMpLiBBbHNvLCAyIDQgMyAxIDUgd2lsbCBwcm9kdWNlIHRoZSBzYW1lIHRyZWUuIEFjdHVhbGx5LCA4IHBlcm11dGF0aW9ucyBhbW9uZyBhbGwgcG9zc2libGUgcGVybXV0YXRpb25zIG9mIHsxLCAyLCAzLCA0LCA1fSB3aWxsIHByb2R1Y2UgdGhlIHNhbWUgdHJlZSB0byB0aGUgdHJlZSBpbiBGaWd1cmUgMShjKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2UgYXJlIGludGVyZXN0ZWQgaW4gZmluZGluZyB0aGUgbnVtYmVyIG9mIHBlcm11dGF0aW9ucyBvZiB7MSwgMiwgJmhlbGxpcDsgLCBOIH0gc3VjaCB0aGF0IGFsbCB0aG9zZSBwZXJtdXRhdGlvbnMgcHJvZHVjZSBhIGJpbmFyeSBzZWFyY2ggdHJlZSBpZGVudGljYWwgdG8gdGhlIHRyZWUgcHJvZHVjZWQgYnkgYSBnaXZlbiBwZXJtdXRhdGlvbiBQIC4gR2l2ZW4gTiBhbmQgUCAsIHlvdSBhcmUgdG8gd3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FsY3VsYXRlcyB0aGUgbnVtYmVyIG9mIHBlcm11dGF0aW9ucyBzYXRpc2Z5aW5nIHRoZSBhYm92ZSBjb25kaXRpb24uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZS4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciBOIHJlcHJlc2VudGluZyB0aGUgbnVtYmVyIG9mIGtleXMsIDEgJmxlOyBOICZsZTsgMjAgLiBJbiB0aGUgbmV4dCBsaW5lLCBhIHBlcm11dGF0aW9uIG9mIGxlbmd0aCBOIGlzIGdpdmVuLiBUaGVyZSBpcyBhIHNpbmdsZSBzcGFjZSBiZXR3ZWVuIHRoZSBpbnRlZ2VycyByZXByZXNlbnRpbmcga2V5cyBpbiB0aGUgcGVybXV0YXRpb248XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZSBhcyBmb2xsb3dzOiBMZXQgQiBiZSB0aGUgbnVtYmVyIG9mIHBlcm11dGF0aW9ucyB0aGF0IHByb2R1Y2UgdGhlIGJpbmFyeSBzZWFyY2ggdHJlZSBpZGVudGljYWwgdG8gdGhlIHRyZWUgcHJvZHVjZWQgYnkgdGhlIGlucHV0IHBlcm11dGF0aW9uLiBQcmludCBCIG1vZCA5LDk5OSw5OTEgZm9yIGVhY2ggdGVzdCBjYXNlLiBGb3IgZXhhbXBsZSwgaWYgQiA9IDIwLDAwMCwwMDAgLCB0aGUgb3V0cHV0IHNob3VsZCBiZSAxOCBmb3IgdGhhdCB0ZXN0IGNhc2UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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