시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB29214612754.043%

문제

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

  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 (≤ 100)가 주어진다. 각 테스트 케이스의 첫째 줄에는 키의 수 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
W3sicHJvYmxlbV9pZCI6Ijg5NDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NzRcdWM5YzQgXHVhYzgwXHVjMGM5IFx1ZDJiOFx1YjlhYyAyIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3NzRcdWM5YzQgXHVhYzgwXHVjMGM5IFx1ZDJiOFx1YjlhY1x1YjI5NCBcdWM3NzRcdWM5YzQgXHVkMmI4XHViOWFjXHVjNzc0XHViMmU0LiBcdWQyYjhcdWI5YWNcdWIyOTQgXHViZTQ0XHVjNWI0XHVjNzg4XHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1YmU0NFx1YzViNFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVkMmI5XHVjOWQ1XHVjNzQ0IFx1YWMwMFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWJhYThcdWI0ZTAgXHViMTc4XHViNGRjXHViMjk0IFx1ZDBhNFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWI0NTAgXHViMTc4XHViNGRjXHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWQwYTRcdWI5N2MgXHVhYzAwXHVjOWM4IFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmU0NFx1YzViNFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVjNjdjXHVjYWJkIFx1YzExY1x1YmUwYyBcdWQyYjhcdWI5YWNcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWQwYTRcdWIyOTQgXHVhZGY4IFx1YzExY1x1YmUwYyBcdWQyYjhcdWI5YWNcdWM3NTggXHViOGU4XHVkMmI4XHVjNzU4IFx1ZDBhNFx1YmNmNFx1YjJlNCBcdWM3OTFcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmU0NFx1YzViNFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzExY1x1YmUwYyBcdWQyYjhcdWI5YWNcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWQwYTRcdWIyOTQgXHVhZGY4IFx1YzExY1x1YmUwYyBcdWQyYjhcdWI5YWNcdWM3NTggXHViOGU4XHVkMmI4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWQwYTRcdWJjZjRcdWIyZTQgXHVkMDZjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM2N2NcdWNhYmQgXHVjMTFjXHViZTBjIFx1ZDJiOFx1YjlhY1x1YzY0MCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjMTFjXHViZTBjIFx1ZDJiOFx1YjlhY1x1YjNjNCBcdWM3NzRcdWM5YzQgXHVhYzgwXHVjMGM5IFx1ZDJiOFx1YjlhY1x1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQwIFx1Yzc3NFx1YzljNCBcdWFjODBcdWMwYzkgXHVkMmI4XHViOWFjXHVjNzU4IFx1YzYwOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90cmVlcGVybS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMjRweDsgd2lkdGg6NTI2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjOWM0IFx1YWM4MFx1YzBjOSBcdWQyYjhcdWI5YWMgVFx1YzVkMFx1YzExYyBrXHVhYzAwIFx1ZDBhNFx1Yzc3OCBcdWIxNzhcdWI0ZGNcdWI5N2MgXHVjYzNlXHVjNzNjXHViODI0XHViYTc0LCBcdWJhM2NcdWM4MDAgXHViOGU4XHVkMmI4XHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFRcdWFjMDAgXHViZTQ0XHVjNWI0XHVjNzg4XHViMmU0XHViYTc0LCBUXHViMjk0IFx1ZDBhNFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjOWMwIFx1YzU0YVx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVhYzgwXHVjMGM5XHVjNzQwIFx1YzJlNFx1ZDMyOFx1ZDU1Y1x1YjJlNC4gXHViZTQ0XHVjNWI0XHVjNzg4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHViOGU4XHVkMmI4XHVjNzU4IFx1ZDBhNFx1YzY0MCBrXHViOTdjIFx1YmU0NFx1YWQ1MFx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBrXHVhYzAwIFx1YjhlOFx1ZDJiOFx1Yzc1OCBcdWQwYTRcdWM2NDAgXHVhYzE5XHViMmU0XHViYTc0LCBcdWFjODBcdWMwYzlcdWM3NDAgXHVjMTMxXHVhY2Y1XHVjODAxXHVjNzNjXHViODVjIFx1Yzg4NVx1YjhjY1x1YjQxY1x1YjJlNC4ga1x1YWMwMCBcdWI4ZThcdWQyYjhcdWM3NTggXHVkMGE0XHViY2Y0XHViMmU0IFx1Yzc5MVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjNjdjXHVjYWJkIFx1YzExY1x1YmUwY1x1ZDJiOFx1YjlhY1x1Yzc1OCBcdWI4ZThcdWQyYjhcdWM1ZDBcdWMxMWMgXHVhYzgwXHVjMGM5XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC4ga1x1YWMwMCBcdWI4ZThcdWQyYjhcdWM3NTggXHVkMGE0XHViY2Y0XHViNGRjIFx1ZDA3MCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzExY1x1YmUwYyBcdWQyYjhcdWI5YWNcdWM3NTggXHViOGU4XHVkMmI4XHVjNWQwXHVjMTFjIFx1YWM4MFx1YzBjOVx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YWMxOVx1Yzc0MCBcdWFjZmNcdWM4MTVcdWM3M2NcdWI4NWMgVFx1Yzc1OCBcdWM2N2NcdWNhYmQgXHViNjEwXHViMjk0IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWMxMWNcdWJlMGMgXHVkMmI4XHViOWFjXHVjNWQwXHVjMTFjIFx1YWM4MFx1YzBjOVx1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YzljNCBcdWFjODBcdWMwYzkgXHVkMmI4XHViOWFjIFRcdWM1ZDAgVFx1YzVkMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWQwYTQga1x1Yjk3YyBcdWMwYmRcdWM3ODVcdWQ1NThcdWI4MjRcdWJhNzQsIFx1YmEzY1x1YzgwMCBUXHVjNWQwXHVjMTFjIGtcdWI5N2MgXHVjYzNlXHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gVFx1YzVkMFx1YjI5NCBrXHVhYzAwIFx1YzVjNlx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YWM4MFx1YzBjOVx1Yzc0MCBcdWMyZTRcdWQzMjhcdWI4NWMgXHViMDVkXHViMGEwIFx1YWM4M1x1Yzc3NFx1YWNlMCwgXHVjMmU0XHVkMzI4XHViODVjIFx1YjA1ZFx1YjA5YyBcdWFkZjggXHVjNzA0XHVjZTU4XHVjNWQwIFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWQwYTQga1x1Yjk3YyBcdWMwYmRcdWM3ODVcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmMgKGEpXHVjNWQwIDgwXHVjNzQ0IFx1YzBiZFx1Yzc4NVx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWI5N2MgXHVjMGI0XHVkM2I0XHViY2Y0XHVjNzkwLiBcdWJhM2NcdWM4MDAsIFx1ZDJiOFx1YjlhY1x1YzVkMFx1YzExYyA4MFx1Yzc0NCBcdWNjM2VcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFjODBcdWMwYzlcdWM3NDAgXHVjMmU0XHVkMzI4XHViODVjIFx1YjA1ZFx1YjA5OFx1YWNlMCwgXHViOWM4XHVjOWMwXHViOWM5XHVjNzNjXHViODVjIFx1YWM4MFx1YzBhY1x1ZDU1YyBcdWQwYTRcdWIyOTQgNDBcdWM3NzRcdWIyZTQuIDgwXHVjNzQ0IFx1YWRmOCBcdWIxNzhcdWI0ZGNcdWM3NTggXHVjNjI0XHViOTc4XHVjYWJkIFx1Yzc5MFx1YzJkZFx1YzczY1x1Yjg1YyBcdWMwYmRcdWM3ODVcdWQ1NThcdWJhNzQsIFx1Yzc3NFx1YzljNCBcdWFjODBcdWMwYzlcdWQyYjhcdWI5YWNcdWIyOTQgKGIpXHVjNjQwIFx1YWMxOVx1YzU0NFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExY1x1YjI5NCAxLCAyLCAuLi4sIE4gXHVjZDFkIE5cdWFjMWNcdWM3NTggXHVkMGE0XHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjNzc0XHVjOWM0IFx1YWM4MFx1YzBjOSBcdWQyYjhcdWI5YWNcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTVjXHViMmU0LiB7MSwgMiwgLi4uLCBOfVx1Yzc1OCBcdWMyMWNcdWM1ZjQgYTxzdWI+MTxcL3N1Yj4sIGE8c3ViPjI8XC9zdWI+LCAuLi4sIGE8c3ViPk48XC9zdWI+XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgYTxzdWI+MTxcL3N1Yj4sIGE8c3ViPjI8XC9zdWI+LCAuLi4sIGE8c3ViPk48XC9zdWI+XHVjNzQ0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWJlNDRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjNzc0XHVjOWM0IFx1YWM4MFx1YzBjOSBcdWQyYjhcdWI5YWNcdWM1ZDAgXHVjMGJkXHVjNzg1XHVkNTVjXHViMmU0XHViYTc0LCBcdWM3NzRcdWM5YzQgXHVhYzgwXHVjMGM5IFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjMjFjXHVjNWY0IDIgMSA0IDMgNVx1YjI5NCBcdWFkZjhcdWI5YmMgKGMpXHViOTdjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI2MTAsIDIgNCAzIDEgNVx1YjNjNCBcdWFjMTlcdWM3NDAgXHVkMmI4XHViOWFjXHViOTdjIFx1YjljY1x1YjRlMFx1YjJlNC4gezEsIDIsIDMsIDQsIDV9XHVjNzU4IFx1YzIxY1x1YzVmNCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVhZGY4XHViOWJjIChjKVx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjNzc0XHVjOWM0IFx1YWM4MFx1YzBjOSBcdWQyYjhcdWI5YWNcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1YzIxY1x1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgOFx1YWMxY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+Tlx1YWNmYyBcdWMyMWNcdWM1ZjQgUFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFkZjggXHVjMjFjXHVjNWY0XHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWM3NzRcdWM5YzQgXHVhYzgwXHVjMGM5IFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVjMjFjXHVjNWY0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVCAoJmxlOyAxMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQwYTRcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAyMCkgXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgTlx1Yzc3OCBcdWMyMWNcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWMyMWNcdWM1ZjRcdWFjZmMgXHVhYzE5XHVjNzQwIFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVjMjFjXHVjNWY0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyA5LDk5OSw5OTFcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiODk0NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJpbmFyeSBTZWFyY2ggVHJlZSIsImRlc2NyaXB0aW9uIjoiPHA+QSBiaW5hcnkgc2VhcmNoIHRyZWUgaXMgYSBiaW5hcnkgdHJlZS4gSXQgbWF5IGJlIGVtcHR5LiBJZiBpdCBpcyBub3QgZW1wdHksIGl0IHNhdGlzZmllcyB0aGUgZm9sbG93aW5nIHByb3BlcnRpZXM6PFwvcD5cclxuXHJcbjxwPkV2ZXJ5IG5vZGUgaGFzIGEga2V5LCBhbmQgbm8gdHdvIG5vZGVzIGhhdmUgdGhlIHNhbWUga2V5LjxiciBcLz5cclxuVGhlIGtleXMgaW4gYSBub25lbXB0eSBsZWZ0IHN1YnRyZWUgbXVzdCBiZSBzbWFsbGVyIHRoYW4gdGhlIGtleSBpbiB0aGUgcm9vdCBvZiB0aGUgc3VidHJlZS48YnIgXC8+XHJcblRoZSBrZXlzIGluIGEgbm9uZW1wdHkgcmlnaHQgc3VidHJlZSBtdXN0IGJlIGxhcmdlciB0aGFuIHRoZSBrZXkgaW4gdGhlIHJvb3Qgb2YgdGhlIHN1YnRyZWUuPGJyIFwvPlxyXG5UaGUgbGVmdCBhbmQgcmlnaHQgc3VidHJlZXMgYXJlIGFsc28gYmluYXJ5IHNlYXJjaCB0cmVlcy48XC9wPlxyXG5cclxuPHA+U2FtcGxlIGJpbmFyeSBzZWFyY2ggdHJlZXMgYXJlIHNob3duIGluIEZpZ3VyZSAxLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RyZWVwZXJtLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIyNHB4OyB3aWR0aDo1MjZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMS4gYmluYXJ5IHNlYXJjaCB0cmVlczxcL3A+XHJcblxyXG48cD5UbyBzZWFyY2ggZm9yIGEgbm9kZSB3aXRoIGEga2V5IGsgaW4gYSBiaW5hcnkgc2VhcmNoIHRyZWUgVCAsIHdlIGJlZ2luIGF0IHRoZSByb290LiBJZiBUIGlzIGVtcHR5LCBUIGNvbnRhaW5zIG5vIGtleXMgYW5kIHRoZSBzZWFyY2ggaXMgdW5zdWNjZXNzZnVsLiBPdGhlcndpc2UsIHdlIGNvbXBhcmUgayB3aXRoIHRoZSBrZXkgaW4gcm9vdC4gSWYgayBlcXVhbHMgcm9vdCZyc3F1bztzIGtleSwgdGhlbiB0aGUgc2VhcmNoIHRlcm1pbmF0ZXMgc3VjY2Vzc2Z1bGx5LiBJZiBrIGlzIGxlc3MgdGhhbiByb290JnJzcXVvO3Mga2V5LCB3ZSBzZWFyY2ggdGhlIGxlZnQgc3VidHJlZSBvZiB0aGUgcm9vdC4gSWYga2lzIGxhcmdlciB0aGFuIHJvb3QmcnNxdW87cyBrZXksIHdlIHNlYXJjaCB0aGUgcmlnaHQgc3VidHJlZSBvZiB0aGUgcm9vdC4gSW4gdGhlIHNhbWUgd2F5LCB3ZSBjYW4gcHJvY2VlZCB0aGUgc2VhcmNoIGluIHRoZSBsZWZ0IG9yIHJpZ2h0IHN1YnJlZSBvZiBUIC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VG8gaW5zZXJ0IGEgbmV3IGtleSBrIGludG8gYSBiaW5hcnkgc2VhcmNoIHRyZWUgVCB3aGVyZSBrIGlzIGRpZmZlcmVudCBmcm9tIHRob3NlIG9mIGV4aXN0aW5nIGtleXMgaW4gVCAsIHdlIGZpcnN0IHNlYXJjaCB0aGUgdHJlZSBUIC4gVGhlIHNlYXJjaCB3aWxsIGJlIHVuc3VjY2Vzc2Z1bCwgdGhlbiB3ZSBpbnNlcnQgdGhlIGtleSBhdCB0aGUgcG9pbnQgdGhlIHNlYXJjaCB0ZXJtaW5hdGVkLiBGb3IgaW5zdGFuY2UsIHRvIGluc2VydCBhIGtleSA4MCBpbnRvIHRoZSBGaWd1cmUgMShhKSwgd2UgZmlyc3Qgc2VhcmNoIHRoZSB0cmVlIGZvciA4MC4gVGhpcyBzZWFyY2ggdGVybWluYXRlcyB1bnN1Y2Nlc3NmdWxseSwgYW5kIHRoZSBsYXN0IG5vZGUgZXhhbWluZWQgaGFzIGtleSA0MC4gV2UgaW5zZXJ0IGEgbmV3IG5vZGUgY29udGFpbmluZyA4MCBhcyB0aGUgcmlnaHQgY2hpbGQgb2YgdGhlIG5vZGUuIFRoZSByZXN1bHRpbmcgc2VhcmNoIHRyZWUgaXMgc2hvd24gaW4gRmlndXJlIDEoYikuPFwvcD5cclxuXHJcbjxwPkluIHRoaXMgcHJvYmxlbSwgd2UgY29uc2lkZXIgYmluYXJ5IHNlYXJjaCB0cmVlcyB3aXRoIE4ga2V5cyAxLCAyLCAuLi4gLCBOIC4gRm9yIGEgcGVybXV0YXRpb24gYTxzdWI+MTxcL3N1Yj4gYTxzdWI+MjxcL3N1Yj4gLi4uIGE8c3ViPk48XC9zdWI+IG9mIHsxLCAyLCAuLi4gLCBOIH0sIGluc2VydGluZyBhPHN1Yj4xPFwvc3ViPiBhPHN1Yj4yPFwvc3ViPiAuLi4gYTxzdWI+TjxcL3N1Yj4gc3VjY2Vzc2l2ZWx5IGludG8gYW4gaW5pdGlhbGx5IGVtcHR5IGJpbmFyeSBzZWFyY2ggdHJlZSB3aWxsIHByb2R1Y2UgYSBiaW5hcnkgc2VhcmNoIHRyZWUuIEZvciBpbnN0YW5jZSwgdGhlIHBlcm11dGF0aW9uIDIgMSA0IDMgNSB3aWxsIHByb2R1Y2UgdGhlIHRyZWUgaW4gRmlndXJlIDEoYykuIEFsc28sIDIgNCAzIDEgNSB3aWxsIHByb2R1Y2UgdGhlIHNhbWUgdHJlZS4gQWN0dWFsbHksIDggcGVybXV0YXRpb25zIGFtb25nIGFsbCBwb3NzaWJsZSBwZXJtdXRhdGlvbnMgb2YgezEsIDIsIDMsIDQsIDV9IHdpbGwgcHJvZHVjZSB0aGUgc2FtZSB0cmVlIHRvIHRoZSB0cmVlIGluIEZpZ3VyZSAxKGMpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5XZSBhcmUgaW50ZXJlc3RlZCBpbiBmaW5kaW5nIHRoZSBudW1iZXIgb2YgcGVybXV0YXRpb25zIG9mIHsxLCAyLCAmaGVsbGlwOyAsIE4gfSBzdWNoIHRoYXQgYWxsIHRob3NlIHBlcm11dGF0aW9ucyBwcm9kdWNlIGEgYmluYXJ5IHNlYXJjaCB0cmVlIGlkZW50aWNhbCB0byB0aGUgdHJlZSBwcm9kdWNlZCBieSBhIGdpdmVuIHBlcm11dGF0aW9uIFAgLiBHaXZlbiBOIGFuZCBQICwgeW91IGFyZSB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzIHRoZSBudW1iZXIgb2YgcGVybXV0YXRpb25zIHNhdGlzZnlpbmcgdGhlIGFib3ZlIGNvbmRpdGlvbi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lLiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyBhbiBpbnRlZ2VyIE4gcmVwcmVzZW50aW5nIHRoZSBudW1iZXIgb2Yga2V5cywgMSAmbGU7IE4gJmxlOyAyMCAuIEluIHRoZSBuZXh0IGxpbmUsIGEgcGVybXV0YXRpb24gb2YgbGVuZ3RoIE4gaXMgZ2l2ZW4uIFRoZXJlIGlzIGEgc2luZ2xlIHNwYWNlIGJldHdlZW4gdGhlIGludGVnZXJzIHJlcHJlc2VudGluZyBrZXlzIGluIHRoZSBwZXJtdXRhdGlvbjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlIGFzIGZvbGxvd3M6IExldCBCIGJlIHRoZSBudW1iZXIgb2YgcGVybXV0YXRpb25zIHRoYXQgcHJvZHVjZSB0aGUgYmluYXJ5IHNlYXJjaCB0cmVlIGlkZW50aWNhbCB0byB0aGUgdHJlZSBwcm9kdWNlZCBieSB0aGUgaW5wdXQgcGVybXV0YXRpb24uIFByaW50IEIgbW9kIDksOTk5LDk5MSBmb3IgZWFjaCB0ZXN0IGNhc2UuIEZvciBleGFtcGxlLCBpZiBCID0gMjAsMDAwLDAwMCAsIHRoZSBvdXRwdXQgc2hvdWxkIGJlIDE4IGZvciB0aGF0IHRlc3QgY2FzZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d