시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 57 24 20 37.736%

문제

마오공 곤돌라는 타이페이의 명소 중 하나이다. 곤돌라 시스템은 원형의 레일과, 하나의 정류장이 있고, 1 부터 n까지 순서대로 번호가 붙은 n개의 곤돌라가 모두 단일한 방향으로 레일을 따라 움직이는 형태이다. i번 곤돌라가 정류장을 지난 직후에는 i+1번 곤돌라가 정류장을 지나가게 된다. (단, i=n번 곤돌라가 지나간 직후에 1 번 곤돌라가 지나가게 된다.)

곤돌라들은 고장이 나기도 한다. 다행히 무제한으로 많은 곤돌라의 여분이 있고, 여분 곤돌라들은 n+1, n+2과 같이 순차적으로 번호가 붙어 있다. 특정한 곤돌라가 고장이 나면 고장난 곤돌라는 빼고, 동일한 위치에 여분 곤돌라를 배치한다. 여분 곤돌라는 작은 번호부터 사용된다. 예를 들어, 사용하는 곤돌라 수가 총 5 개이고, 1 번 곤돌라가 고장난다면, 그 곤돌라는 6번으로 교체된다.

당신은 정류장에 서서 곤돌라들이 지나가는 것을 즐겨 본다. 곤돌라 수열이라는 것은 임의의 시점에서 시작해서 정류장을 지나가는 n개의 곤돌라들의 번호를 순서대로 적은 것이다. 곤돌라 수열을 적기 시작하는 시점 이전에 이미 몇개의 곤돌라가 고장나서 교체되었을 수 있다. 하지만, 곤돌라 수열을 적는 도중에는 아무 곤돌라도 고장이 나지 않는다.

전체적으로 곤돌라들의 배치가 동일하더라도 어떤 시점에 곤돌라 수열을 적기 시작하느냐에 따라 서로 다른 곤돌라 수열이 나올수 있다는 점에 주의하자. 예를 들어, 총 5개의 곤돌라들 중 고장난 곤돌라가 없는 경우에 (2, 3, 4, 5, 1) 과 (4, 5, 1, 2, 3) 은 모두 가능한 곤돌라 수열들이다. 하지만, 이경우 (4, 3, 2, 5, 1) 은 가능한 곤돌라 수열이 아니다. (곤돌라 번호의 순서가 잘못되어 있다.)

만약 곤돌라 1번 만이 고장난 상황이라면, (4, 5, 6, 2, 3) 의 곤돌라 수열을 만들 수 있다. 만약 이후 4번 곤돌라가 고장난다면, 7번 곤돌라가 그 자리에 있게 되고, (6, 2, 3, 7, 5) 가 가능한 곤돌라 수열이 된다. 만약 7번 곤돌라가 이후에 고장이 난다면, 8번이 그 자리를 차지할 것이고 (3, 8, 5, 6, 2) 가 가능한 곤돌라 수열들 중 하나가 된다.

고장난 곤돌라 새 곤돌라 가능한 곤돌라 수열 중 하나
1 6 (4, 5, 6, 2, 3)
4 7 (6, 2, 3, 7, 5)
7 8 (3, 8, 5, 6, 2)

교체 수열이라는 것은 고장난 곤돌라들의 번호를 고장난 순서에 따라 쓴 것이다. 직전의 예에서 교체 수열은 (1, 4, 7) 이다. 교체 수열 e이 곤돌라 수열 g를 만든다고 말을 할 수 있는데, 그것은 초기 상황에서 시작해서 r에 해당하는 방법으로 곤돌라들이 고장난 직후에, g가 가능한 곤돌라 수열들 중 하나인 경우를 의미한다.

이 문제에서는 주어진 수열(가능한 곤돌라 수열일 수도 아닐 수도 있음)을 만들 수 있는 교체 수열의 수를 세어서 그 값을 1,000,000,009 로 나눈 나머지를 계산해야 한다. 다음과 같이 선언된 함수 countReplacement 를 구현해야 한다.

  • countReplacement(n, inputSeq)
    • n: 입력 수열의 길이.
    • inputSeq: 크기 인 배열; inputSeq[i]는 입력 수열의 번 원소이다 (0 ≤ i ≤ n-1).
    • 입력이 곤돌라 수열인 경우, 입력의 곤돌라 수열을 만들 수 있는 모든 교체 수열의 수를 센 다음에 (그 수는 매우 클수 있음) 그 결과를 1,000,000,009 로 나눈 나머지를 리턴해야 한다. 만약 입력이 곤돌라 수열이 아닌 경우 0을 리턴해야 한다. 입력이 곤돌라 수열이고 고장난 곤돌라가 하나도 없는 경우는 1을 리턴해야 한다.

입력

첫째 줄에 입력 수열의 길이 n이 주어진다. (1 ≤ n ≤ 100,000)

둘째 줄에는 inputSeq[0], ..., inputSeq[n-1]이 주어진다. (1 ≤ inputSeq[i] ≤ 1,000,000,000)

출력

countReplacement함수의 리턴값을 출력한다.

예제 입력 1

4
1 2 7 6

예제 출력 1

2

힌트

inputSeq 리턴 값 교체 수열
(1, 2, 7, 6) 2 (3, 4, 5) or (4, 5, 3)
(2, 3, 4, 12, 6, 7, 1) 1 (5, 8, 9, 10, 11)
(4, 7, 4, 7) 0 inputSeq가 곤돌라 수열이 아님
(3, 4) 2 (1, 2) or (2, 1)
W3sicHJvYmxlbV9pZCI6IjEwMDc0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhY2U0XHViM2NjXHViNzdjIC0gXHVhZDUwXHVjY2I0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMTggXHVjMTM4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWI5YzhcdWM2MjRcdWFjZjUgXHVhY2U0XHViM2NjXHViNzdjXHViMjk0IFx1ZDBjMFx1Yzc3NFx1ZDM5OFx1Yzc3NFx1Yzc1OCBcdWJhODVcdWMxOGMgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YjJlNC4gXHVhY2U0XHViM2NjXHViNzdjIFx1YzJkY1x1YzJhNFx1ZDE1Y1x1Yzc0MCBcdWM2ZDBcdWQ2MTVcdWM3NTggXHViODA4XHVjNzdjXHVhY2ZjLCBcdWQ1NThcdWIwOThcdWM3NTggXHVjODE1XHViOTU4XHVjN2E1XHVjNzc0IFx1Yzc4OFx1YWNlMCwgMSBcdWJkODBcdWQxMzAgblx1YWU0Y1x1YzljMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViYzg4XHVkNjM4XHVhYzAwIFx1YmQ5OVx1Yzc0MCBuXHVhYzFjXHVjNzU4IFx1YWNlNFx1YjNjY1x1Yjc3Y1x1YWMwMCBcdWJhYThcdWI0NTAgXHViMmU4XHVjNzdjXHVkNTVjIFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWI4MDhcdWM3N2NcdWM3NDQgXHViNTMwXHViNzdjIFx1YzZjMFx1YzljMVx1Yzc3NFx1YjI5NCBcdWQ2MTVcdWQwZGNcdWM3NzRcdWIyZTQuIGlcdWJjODggXHVhY2U0XHViM2NjXHViNzdjXHVhYzAwIFx1YzgxNVx1Yjk1OFx1YzdhNVx1Yzc0NCBcdWM5YzBcdWIwOWMgXHVjOWMxXHVkNmM0XHVjNWQwXHViMjk0IGkrMVx1YmM4OCBcdWFjZTRcdWIzY2NcdWI3N2NcdWFjMDAgXHVjODE1XHViOTU4XHVjN2E1XHVjNzQ0IFx1YzljMFx1YjA5OFx1YWMwMFx1YWM4YyBcdWI0MWNcdWIyZTQuIChcdWIyZTgsIGk9blx1YmM4OCBcdWFjZTRcdWIzY2NcdWI3N2NcdWFjMDAgXHVjOWMwXHViMDk4XHVhYzA0IFx1YzljMVx1ZDZjNFx1YzVkMCAxIFx1YmM4OCBcdWFjZTRcdWIzY2NcdWI3N2NcdWFjMDAgXHVjOWMwXHViMDk4XHVhYzAwXHVhYzhjIFx1YjQxY1x1YjJlNC4pPFwvcD5cclxuXHJcbjxwPlx1YWNlNFx1YjNjY1x1Yjc3Y1x1YjRlNFx1Yzc0MCBcdWFjZTBcdWM3YTVcdWM3NzQgXHViMDk4XHVhZTMwXHViM2M0IFx1ZDU1Y1x1YjJlNC4gXHViMmU0XHVkNTg5XHVkNzg4IFx1YmIzNFx1YzgxY1x1ZDU1Y1x1YzczY1x1Yjg1YyBcdWI5Y2VcdWM3NDAgXHVhY2U0XHViM2NjXHViNzdjXHVjNzU4IFx1YzVlY1x1YmQ4NFx1Yzc3NCBcdWM3ODhcdWFjZTAsIFx1YzVlY1x1YmQ4NCBcdWFjZTRcdWIzY2NcdWI3N2NcdWI0ZTRcdWM3NDAgbisxLCBuKzJcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YzIxY1x1Y2MyOFx1YzgwMVx1YzczY1x1Yjg1YyBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDk5XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVkMmI5XHVjODE1XHVkNTVjIFx1YWNlNFx1YjNjY1x1Yjc3Y1x1YWMwMCBcdWFjZTBcdWM3YTVcdWM3NzQgXHViMDk4XHViYTc0IFx1YWNlMFx1YzdhNVx1YjA5YyBcdWFjZTRcdWIzY2NcdWI3N2NcdWIyOTQgXHViZTdjXHVhY2UwLCBcdWIzZDlcdWM3N2NcdWQ1NWMgXHVjNzA0XHVjZTU4XHVjNWQwIFx1YzVlY1x1YmQ4NCBcdWFjZTRcdWIzY2NcdWI3N2NcdWI5N2MgXHViYzMwXHVjZTU4XHVkNTVjXHViMmU0LiBcdWM1ZWNcdWJkODQgXHVhY2U0XHViM2NjXHViNzdjXHViMjk0IFx1Yzc5MVx1Yzc0MCBcdWJjODhcdWQ2MzhcdWJkODBcdWQxMzAgXHVjMGFjXHVjNmE5XHViNDFjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWMwYWNcdWM2YTlcdWQ1NThcdWIyOTQgXHVhY2U0XHViM2NjXHViNzdjIFx1YzIxOFx1YWMwMCBcdWNkMWQgNSBcdWFjMWNcdWM3NzRcdWFjZTAsIDEgXHViYzg4IFx1YWNlNFx1YjNjY1x1Yjc3Y1x1YWMwMCBcdWFjZTBcdWM3YTVcdWIwOWNcdWIyZTRcdWJhNzQsIFx1YWRmOCBcdWFjZTRcdWIzY2NcdWI3N2NcdWIyOTQgNlx1YmM4OFx1YzczY1x1Yjg1YyBcdWFkNTBcdWNjYjRcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJmOVx1YzJlMFx1Yzc0MCBcdWM4MTVcdWI5NThcdWM3YTVcdWM1ZDAgXHVjMTFjXHVjMTFjIFx1YWNlNFx1YjNjY1x1Yjc3Y1x1YjRlNFx1Yzc3NCBcdWM5YzBcdWIwOThcdWFjMDBcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzk5MFx1YWNhOCBcdWJjZjhcdWIyZTQuIFx1YWNlNFx1YjNjY1x1Yjc3YyBcdWMyMThcdWM1ZjRcdWM3NzRcdWI3N2NcdWIyOTQgXHVhYzgzXHVjNzQwIFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWMyZGNcdWM4MTBcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTc0XHVjMTFjIFx1YzgxNVx1Yjk1OFx1YzdhNVx1Yzc0NCBcdWM5YzBcdWIwOThcdWFjMDBcdWIyOTQgblx1YWMxY1x1Yzc1OCBcdWFjZTRcdWIzY2NcdWI3N2NcdWI0ZTRcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4MDFcdWM3NDAgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWFjZTRcdWIzY2NcdWI3N2MgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YzgwMVx1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTQgXHVjMmRjXHVjODEwIFx1Yzc3NFx1YzgwNFx1YzVkMCBcdWM3NzRcdWJiZjggXHViYTg3XHVhYzFjXHVjNzU4IFx1YWNlNFx1YjNjY1x1Yjc3Y1x1YWMwMCBcdWFjZTBcdWM3YTVcdWIwOThcdWMxMWMgXHVhZDUwXHVjY2I0XHViNDE4XHVjNWM4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVhY2U0XHViM2NjXHViNzdjIFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWM4MDFcdWIyOTQgXHViM2M0XHVjOTExXHVjNWQwXHViMjk0IFx1YzU0NFx1YmIzNCBcdWFjZTRcdWIzY2NcdWI3N2NcdWIzYzQgXHVhY2UwXHVjN2E1XHVjNzc0IFx1YjA5OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzgwNFx1Y2NiNFx1YzgwMVx1YzczY1x1Yjg1YyBcdWFjZTRcdWIzY2NcdWI3N2NcdWI0ZTRcdWM3NTggXHViYzMwXHVjZTU4XHVhYzAwIFx1YjNkOVx1Yzc3Y1x1ZDU1OFx1YjM1NFx1Yjc3Y1x1YjNjNCBcdWM1YjRcdWI1YTQgXHVjMmRjXHVjODEwXHVjNWQwIFx1YWNlNFx1YjNjY1x1Yjc3YyBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjODAxXHVhZTMwIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5MFx1YjBkMFx1YzVkMCBcdWI1MzBcdWI3N2MgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWFjZTRcdWIzY2NcdWI3N2MgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YjA5OFx1YzYyY1x1YzIxOCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVjODEwXHVjNWQwIFx1YzhmY1x1Yzc1OFx1ZDU1OFx1Yzc5MC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjZDFkIDVcdWFjMWNcdWM3NTggXHVhY2U0XHViM2NjXHViNzdjXHViNGU0IFx1YzkxMSBcdWFjZTBcdWM3YTVcdWIwOWMgXHVhY2U0XHViM2NjXHViNzdjXHVhYzAwIFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDAgKDIsIDMsIDQsIDUsIDEpIFx1YWNmYyAoNCwgNSwgMSwgMiwgMykgXHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVhY2U0XHViM2NjXHViNzdjIFx1YzIxOFx1YzVmNFx1YjRlNFx1Yzc3NFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWM3NzRcdWFjYmRcdWM2YjAgKDQsIDMsIDIsIDUsIDEpIFx1Yzc0MCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVhY2U0XHViM2NjXHViNzdjIFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuIChcdWFjZTRcdWIzY2NcdWI3N2MgXHViYzg4XHVkNjM4XHVjNzU4IFx1YzIxY1x1YzExY1x1YWMwMCBcdWM3OThcdWJhYmJcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0Lik8XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkIFx1YWNlNFx1YjNjY1x1Yjc3YyAxXHViYzg4IFx1YjljY1x1Yzc3NCBcdWFjZTBcdWM3YTVcdWIwOWMgXHVjMGMxXHVkNjY5XHVjNzc0XHViNzdjXHViYTc0LCAoNCwgNSwgNiwgMiwgMykgXHVjNzU4IFx1YWNlNFx1YjNjY1x1Yjc3YyBcdWMyMThcdWM1ZjRcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWM3NzRcdWQ2YzQgNFx1YmM4OCBcdWFjZTRcdWIzY2NcdWI3N2NcdWFjMDAgXHVhY2UwXHVjN2E1XHViMDljXHViMmU0XHViYTc0LCA3XHViYzg4IFx1YWNlNFx1YjNjY1x1Yjc3Y1x1YWMwMCBcdWFkZjggXHVjNzkwXHViOWFjXHVjNWQwIFx1Yzc4OFx1YWM4YyBcdWI0MThcdWFjZTAsICg2LCAyLCAzLCA3LCA1KSBcdWFjMDAgXHVhYzAwXHViMmE1XHVkNTVjIFx1YWNlNFx1YjNjY1x1Yjc3YyBcdWMyMThcdWM1ZjRcdWM3NzQgXHViNDFjXHViMmU0LiBcdWI5Y2NcdWM1N2QgN1x1YmM4OCBcdWFjZTRcdWIzY2NcdWI3N2NcdWFjMDAgXHVjNzc0XHVkNmM0XHVjNWQwIFx1YWNlMFx1YzdhNVx1Yzc3NCBcdWIwOWNcdWIyZTRcdWJhNzQsIDhcdWJjODhcdWM3NzQgXHVhZGY4IFx1Yzc5MFx1YjlhY1x1Yjk3YyBcdWNjMjhcdWM5YzBcdWQ1NjAgXHVhYzgzXHVjNzc0XHVhY2UwICgzLCA4LCA1LCA2LCAyKSBcdWFjMDAgXHVhYzAwXHViMmE1XHVkNTVjIFx1YWNlNFx1YjNjY1x1Yjc3YyBcdWMyMThcdWM1ZjRcdWI0ZTQgXHVjOTExIFx1ZDU1OFx1YjA5OFx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDo0MCVcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5cdWFjZTBcdWM3YTVcdWIwOWMgXHVhY2U0XHViM2NjXHViNzdjPFwvdGg+XHJcblx0XHRcdDx0aD5cdWMwYzggXHVhY2U0XHViM2NjXHViNzdjPFwvdGg+XHJcblx0XHRcdDx0aD5cdWFjMDBcdWIyYTVcdWQ1NWMgXHVhY2U0XHViM2NjXHViNzdjIFx1YzIxOFx1YzVmNCBcdWM5MTEgXHVkNTU4XHViMDk4PFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjY8XC90ZD5cclxuXHRcdFx0PHRkPig0LCA1LCA2LCAyLCAzKTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD40PFwvdGQ+XHJcblx0XHRcdDx0ZD43PFwvdGQ+XHJcblx0XHRcdDx0ZD4oNiwgMiwgMywgNywgNSk8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+NzxcL3RkPlxyXG5cdFx0XHQ8dGQ+ODxcL3RkPlxyXG5cdFx0XHQ8dGQ+KDMsIDgsIDUsIDYsIDIpPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5cdWFkNTBcdWNjYjQgXHVjMjE4XHVjNWY0XHVjNzc0XHViNzdjXHViMjk0IFx1YWM4M1x1Yzc0MCBcdWFjZTBcdWM3YTVcdWIwOWMgXHVhY2U0XHViM2NjXHViNzdjXHViNGU0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWFjZTBcdWM3YTVcdWIwOWMgXHVjMjFjXHVjMTFjXHVjNWQwIFx1YjUzMFx1Yjc3YyBcdWM0ZjQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM5YzFcdWM4MDRcdWM3NTggXHVjNjA4XHVjNWQwXHVjMTFjIFx1YWQ1MFx1Y2NiNCBcdWMyMThcdWM1ZjRcdWM3NDAgKDEsIDQsIDcpIFx1Yzc3NFx1YjJlNC4gXHVhZDUwXHVjY2I0IFx1YzIxOFx1YzVmNCBlXHVjNzc0IFx1YWNlNFx1YjNjY1x1Yjc3YyBcdWMyMThcdWM1ZjQgZ1x1Yjk3YyBcdWI5Y2NcdWI0ZTBcdWIyZTRcdWFjZTAgXHViOWQwXHVjNzQ0IFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHViMzcwLCBcdWFkZjhcdWFjODNcdWM3NDAgXHVjZDA4XHVhZTMwIFx1YzBjMVx1ZDY2OVx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NzRcdWMxMWMgclx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YWNlNFx1YjNjY1x1Yjc3Y1x1YjRlNFx1Yzc3NCBcdWFjZTBcdWM3YTVcdWIwOWMgXHVjOWMxXHVkNmM0XHVjNWQwLCBnXHVhYzAwIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjZTRcdWIzY2NcdWI3N2MgXHVjMjE4XHVjNWY0XHViNGU0IFx1YzkxMSBcdWQ1NThcdWIwOThcdWM3NzggXHVhY2JkXHVjNmIwXHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExY1x1YjI5NCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0KFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjZTRcdWIzY2NcdWI3N2MgXHVjMjE4XHVjNWY0XHVjNzdjIFx1YzIxOFx1YjNjNCBcdWM1NDRcdWIyZDAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1Yzc0YylcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhZDUwXHVjY2I0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjMTM4XHVjNWI0XHVjMTFjIFx1YWRmOCBcdWFjMTJcdWM3NDQgMSwwMDAsMDAwLDAwOSBcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YzEyMFx1YzViOFx1YjQxYyBcdWQ1NjhcdWMyMTggY291bnRSZXBsYWNlbWVudCBcdWI5N2MgXHVhZDZjXHVkNjA0XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5jb3VudFJlcGxhY2VtZW50KG4sIGlucHV0U2VxKVxyXG5cdDx1bD5cclxuXHRcdDxsaT5uOiBcdWM3ODVcdWI4MjUgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NC48XC9saT5cclxuXHRcdDxsaT5pbnB1dFNlcTogXHVkMDZjXHVhZTMwIFx1Yzc3OCBcdWJjMzBcdWM1ZjQ7IGlucHV0U2VxW2ldXHViMjk0IFx1Yzc4NVx1YjgyNSBcdWMyMThcdWM1ZjRcdWM3NTggXHViYzg4IFx1YzZkMFx1YzE4Y1x1Yzc3NFx1YjJlNCAoMCAmbGU7IGkgJmxlOyBuLTEpLjxcL2xpPlxyXG5cdFx0PGxpPlx1Yzc4NVx1YjgyNVx1Yzc3NCBcdWFjZTRcdWIzY2NcdWI3N2MgXHVjMjE4XHVjNWY0XHVjNzc4IFx1YWNiZFx1YzZiMCwgXHVjNzg1XHViODI1XHVjNzU4IFx1YWNlNFx1YjNjY1x1Yjc3YyBcdWMyMThcdWM1ZjRcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1YWQ1MFx1Y2NiNCBcdWMyMThcdWM1ZjRcdWM3NTggXHVjMjE4XHViOTdjIFx1YzEzYyBcdWIyZTRcdWM3NGNcdWM1ZDAgKFx1YWRmOCBcdWMyMThcdWIyOTQgXHViOWU0XHVjNmIwIFx1ZDA3NFx1YzIxOCBcdWM3ODhcdWM3NGMpIFx1YWRmOCBcdWFjYjBcdWFjZmNcdWI5N2MgMSwwMDAsMDAwLDAwOSBcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWI5YWNcdWQxMzRcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVjNzg1XHViODI1XHVjNzc0IFx1YWNlNFx1YjNjY1x1Yjc3YyBcdWMyMThcdWM1ZjRcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YWNiZFx1YzZiMCAwXHVjNzQ0IFx1YjlhY1x1ZDEzNFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc3NCBcdWFjZTRcdWIzY2NcdWI3N2MgXHVjMjE4XHVjNWY0XHVjNzc0XHVhY2UwIFx1YWNlMFx1YzdhNVx1YjA5YyBcdWFjZTRcdWIzY2NcdWI3N2NcdWFjMDAgXHVkNTU4XHViMDk4XHViM2M0IFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgMVx1Yzc0NCBcdWI5YWNcdWQxMzRcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxcL3VsPlxyXG5cdDxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzc4NVx1YjgyNSBcdWMyMThcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IG4gJmxlOyAxMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IGlucHV0U2VxWzBdLCAuLi4sIGlucHV0U2VxW24tMV1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IGlucHV0U2VxW2ldICZsZTsgMSwwMDAsMDAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5jb3VudFJlcGxhY2VtZW50XHVkNTY4XHVjMjE4XHVjNzU4IFx1YjlhY1x1ZDEzNFx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6Ijx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDo1MCVcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5pbnB1dFNlcTxcL3RoPlxyXG5cdFx0XHQ8dGg+XHViOWFjXHVkMTM0IFx1YWMxMjxcL3RoPlxyXG5cdFx0XHQ8dGg+XHVhZDUwXHVjY2I0IFx1YzIxOFx1YzVmNDxcL3RoPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGhlYWQ+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+KDEsIDIsIDcsIDYpPFwvdGQ+XHJcblx0XHRcdDx0ZD4yPFwvdGQ+XHJcblx0XHRcdDx0ZD4oMywgNCwgNSkgb3IgKDQsIDUsIDMpPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPigyLCAzLCA0LCAxMiwgNiwgNywgMSk8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPig1LCA4LCA5LCAxMCwgMTEpPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPig0LCA3LCA0LCA3KTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+aW5wdXRTZXFcdWFjMDAgXHVhY2U0XHViM2NjXHViNzdjIFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM1NDRcdWIyZDg8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+KDMsIDQpPFwvdGQ+XHJcblx0XHRcdDx0ZD4yPFwvdGQ+XHJcblx0XHRcdDx0ZD4oMSwgMikgb3IgKDIsIDEpPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTAwNzQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHb25kb2xhIC0gQ291bnQgUmVwbGFjZW1lbnQgU2VxdWVuY2VzIiwiZGVzY3JpcHRpb24iOiI8cD5NYW8tS29uZyBHb25kb2xhIGlzIGEgZmFtb3VzIGF0dHJhY3Rpb24gaW4gVGFpcGVpLiBUaGUgZ29uZG9sYSBzeXN0ZW0gY29uc2lzdHMgb2YgYSBjaXJjdWxhciByYWlsLCBhIHNpbmdsZSBzdGF0aW9uLCBhbmQgbiBnb25kb2xhcyBudW1iZXJlZCBjb25zZWN1dGl2ZWx5IGZyb20gMSB0byBuIHJ1bm5pbmcgYXJvdW5kIHRoZSByYWlsIGluIGEgZml4ZWQgZGlyZWN0aW9uLiBBZnRlciBnb25kb2xhIGkgcGFzc2VzIHRoZSBzdGF0aW9uLCB0aGUgbmV4dCBnb25kb2xhIHRvIHBhc3MgdGhlIHN0YXRpb24gd2lsbCBiZSBnb25kb2xhIGkrMSBpZiBpICZsdDsgbiwgb3IgZ29uZG9sYSAxIGlmIGkgPSBuLjxcL3A+XHJcblxyXG48cD5Hb25kb2xhcyBtYXkgYnJlYWsgZG93bi4gTHVja2lseSB3ZSBoYXZlIGFuIGluZmluaXRlIHN1cHBseSBvZiBzcGFyZSBnb25kb2xhcywgd2hpY2ggYXJlIG51bWJlcmVkIG4rMSwgbisyLCBhbmQgc28gb24uIFdoZW4gYSBnb25kb2xhIGJyZWFrcyBkb3duIHdlIHJlcGxhY2UgaXQgKGluIHRoZSBzYW1lIHBvc2l0aW9uIG9uIHRoZSB0cmFjaykgd2l0aCB0aGUgZmlyc3QgYXZhaWxhYmxlIHNwYXJlIGdvbmRvbGEsIHRoYXQgaXMsIHRoZSBvbmUgd2l0aCB0aGUgbG93ZXN0IG51bWJlci4gRm9yIGV4YW1wbGUsIGlmIHRoZXJlIGFyZSBmaXZlIGdvbmRvbGFzIGFuZCBnb25kb2xhIDEgYnJlYWtzIGRvd24sIHRoZW4gd2Ugd2lsbCByZXBsYWNlIGl0IHdpdGggZ29uZG9sYSA2LjxcL3A+XHJcblxyXG48cD5Zb3UgbGlrZSB0byBzdGFuZCBhdCB0aGUgc3RhdGlvbiBhbmQgd2F0Y2ggdGhlIGdvbmRvbGFzIGFzIHRoZXkgcGFzcyBieS4gQSBnb25kb2xhIHNlcXVlbmNlIGlzIGEgc2VxdWVuY2Ugb2YgbiBudW1iZXJzIG9mIGdvbmRvbGFzIHRoYXQgcGFzcyB0aGUgc3RhdGlvbi4gSXQgaXMgcG9zc2libGUgdGhhdCBvbmUgb3IgbW9yZSBnb25kb2xhcyBicm9rZSBkb3duIChhbmQgd2VyZSByZXBsYWNlZCkgYmVmb3JlIHlvdSBhcnJpdmVkLCBidXQgbm9uZSBvZiB0aGUgZ29uZG9sYXMgYnJlYWsgZG93biB3aGlsZSB5b3UgYXJlIHdhdGNoaW5nLjxcL3A+XHJcblxyXG48cD5Ob3RlIHRoYXQgdGhlIHNhbWUgY29uZmlndXJhdGlvbiBvZiBnb25kb2xhcyBvbiB0aGUgcmFpbCBjYW4gZ2l2ZSBtdWx0aXBsZSBnb25kb2xhIHNlcXVlbmNlcywgZGVwZW5kaW5nIG9uIHdoaWNoIGdvbmRvbGEgcGFzc2VzIGZpcnN0IHdoZW4geW91IGFycml2ZSBhdCB0aGUgc3RhdGlvbi4gRm9yIGV4YW1wbGUsIGlmIG5vbmUgb2YgdGhlIGdvbmRvbGFzIGhhdmUgYnJva2VuIGRvd24gdGhlbiBib3RoICgyLCAzLCA0LCA1LCAxKSBhbmQgKDQsIDUsIDEsIDIsIDMpIGFyZSBwb3NzaWJsZSBnb25kb2xhIHNlcXVlbmNlcywgYnV0ICg0LCAzLCAyLCA1LCAxKSBpcyBub3QgKGJlY2F1c2UgdGhlIGdvbmRvbGFzIGFwcGVhciBpbiB0aGUgd3Jvbmcgb3JkZXIpLjxcL3A+XHJcblxyXG48cD5JZiBnb25kb2xhIDEgYnJlYWtzIGRvd24sIHRoZW4gd2UgbWlnaHQgbm93IG9ic2VydmUgdGhlIGdvbmRvbGEgc2VxdWVuY2UgKDQsIDUsIDYsIDIsIDMpLiBJZiBnb25kb2xhIDQgYnJlYWtzIGRvd24gbmV4dCwgd2UgcmVwbGFjZSBpdCB3aXRoIGdvbmRvbGEgNyBhbmQgd2UgbWlnaHQgb2JzZXJ2ZSB0aGUgZ29uZG9sYSBzZXF1ZW5jZSAoNiwgMiwgMywgNywgNSkuIElmIGdvbmRvbGEgNyBicmVha3MgZG93biBhZnRlciB0aGlzLCB3ZSByZXBsYWNlIGl0IHdpdGggZ29uZG9sYSA4IGFuZCB3ZSBtYXkgbm93IG9ic2VydmUgdGhlIGdvbmRvbGEgc2VxdWVuY2UgKDMsIDgsIDUsIDYsIDIpLjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6NDAlXCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+YnJva2VuIGdvbmRvbGE8XC90aD5cclxuXHRcdFx0PHRoPm5ldyBnb25kb2xhPFwvdGg+XHJcblx0XHRcdDx0aD5wb3NzaWJsZSBnb25kb2xhIHNlcXVlbmNlPFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjY8XC90ZD5cclxuXHRcdFx0PHRkPig0LCA1LCA2LCAyLCAzKTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD40PFwvdGQ+XHJcblx0XHRcdDx0ZD43PFwvdGQ+XHJcblx0XHRcdDx0ZD4oNiwgMiwgMywgNywgNSk8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+NzxcL3RkPlxyXG5cdFx0XHQ8dGQ+ODxcL3RkPlxyXG5cdFx0XHQ8dGQ+KDMsIDgsIDUsIDYsIDIpPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5BIHJlcGxhY2VtZW50IHNlcXVlbmNlIGlzIGEgc2VxdWVuY2UgY29uc2lzdGluZyBvZiB0aGUgbnVtYmVycyBvZiB0aGUgZ29uZG9sYXMgdGhhdCBoYXZlIGJyb2tlbiBkb3duLCBpbiB0aGUgb3JkZXIgaW4gd2hpY2ggdGhleSBicmVhayBkb3duLiBJbiB0aGUgcHJldmlvdXMgZXhhbXBsZSB0aGUgcmVwbGFjZW1lbnQgc2VxdWVuY2UgaXMgKDEsIDQsIDcpLiBBIHJlcGxhY2VtZW50IHNlcXVlbmNlIHIgcHJvZHVjZXMgYSBnb25kb2xhIHNlcXVlbmNlIGcgaWYsIGFmdGVyIGdvbmRvbGFzIGJyZWFrIGRvd24gYWNjb3JkaW5nIHRvIHRoZSByZXBsYWNlbWVudCBzZXF1ZW5jZSByLCB0aGUgZ29uZG9sYSBzZXF1ZW5jZSBnIG1heSBiZSBvYnNlcnZlZC48XC9wPlxyXG5cclxuPHA+WW91IG11c3QgY291bnQgdGhlIG51bWJlciBvZiBwb3NzaWJsZSByZXBsYWNlbWVudCBzZXF1ZW5jZXMgdGhhdCBwcm9kdWNlIGEgZ2l2ZW4gc2VxdWVuY2UgKHdoaWNoIG1heSBvciBtYXkgbm90IGJlIGEgZ29uZG9sYSBzZXF1ZW5jZSksIG1vZHVsbyAxLDAwMCwwMDAsMDA5LiBZb3UgbmVlZCB0byBpbXBsZW1lbnQgYSBmdW5jdGlvbiBjb3VudFJlcGxhY2VtZW50LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPmNvdW50UmVwbGFjZW1lbnQobiwgaW5wdXRTZXEpXHJcblx0PHVsPlxyXG5cdFx0PGxpPm46IHRoZSBsZW5ndGggb2YgdGhlIGlucHV0IHNlcXVlbmNlLjxcL2xpPlxyXG5cdFx0PGxpPmlucHV0U2VxOiBhcnJheSBvZiBsZW5ndGggOyBpbnB1dFNlcVtpXSBpcyBlbGVtZW50IG9mIHRoZSBpbnB1dCBzZXF1ZW5jZSwgZm9yIDAgJmxlOyBpICZsZTsgbi0xLjxcL2xpPlxyXG5cdFx0PGxpPklmIHRoZSBpbnB1dCBzZXF1ZW5jZSBpcyBhIGdvbmRvbGEgc2VxdWVuY2UsIHRoZW4gY291bnQgdGhlIG51bWJlciBvZiByZXBsYWNlbWVudCBzZXF1ZW5jZXMgdGhhdCBwcm9kdWNlIHRoaXMgZ29uZG9sYSBzZXF1ZW5jZSAod2hpY2ggY291bGQgYmUgZXh0cmVtZWx5IGxhcmdlKSwgYW5kIHJldHVybiB0aGlzIG51bWJlciBtb2R1bG8gMSwwMDAsMDAwLDAwOS4gSWYgdGhlIGlucHV0IHNlcXVlbmNlIGlzIG5vdCBhIGdvbmRvbGEgc2VxdWVuY2UsIHRoZSBmdW5jdGlvbiBzaG91bGQgcmV0dXJuIDAuIElmIHRoZSBpbnB1dCBzZXF1ZW5jZSBpcyBhIGdvbmRvbGEgc2VxdWVuY2UgYnV0IG5vIGdvbmRvbGFzIGJyb2tlIGRvd24sIHRoZSBmdW5jdGlvbiBzaG91bGQgcmV0dXJuIDEuPFwvbGk+XHJcblx0PFwvdWw+XHJcblx0PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPmxpbmUgMTogbiwgdGhlIGxlbmd0aCBvZiB0aGUgaW5wdXQgc2VxdWVuY2UuPFwvcD5cclxuXHJcbjxwPmxpbmUgMjogdGhpcyBsaW5lIGNvbnRhaW5zIGlucHV0U2VxWzBdLCAuLi4sIGlucHV0U2VxW24tMV0uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgcmV0dXJuIHZhbHVlIG9mIGZ1bmN0aW9uIGNvdW50UmVwbGFjZW1lbnQuPFwvcD5cclxuIiwiaGludCI6Ijx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDo0MTFweFwiPlxyXG5cdDx0aGVhZD5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPmlucHV0U2VxPFwvdGg+XHJcblx0XHRcdDx0aD5yZXR1cm4gdmFsdWU8XC90aD5cclxuXHRcdFx0PHRoPnJlcGxhY2VtZW50IHNlcXVlbmNlPFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4oMSwgMiwgNywgNik8XC90ZD5cclxuXHRcdFx0PHRkPjI8XC90ZD5cclxuXHRcdFx0PHRkPigzLCA0LCA1KSBvciAoNCwgNSwgMyk8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+KDIsIDMsIDQsIDEyLCA2LCA3LCAxKTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+KDUsIDgsIDksIDEwLCAxMSk8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+KDQsIDcsIDQsIDcpPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD5pbnB1dFNlcSBpcyBub3QgYSBnb25kb2xhIHNlcXVlbmNlPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPigzLCA0KTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MjxcL3RkPlxyXG5cdFx0XHQ8dGQ+KDEsIDIpIG9yICgyLCAxKTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==