시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB299594931.410%

문제

지승이는 대학교에서 수학을 가르치고 있다. 이번학기에는 "이산 수학과 조합론"을 가르치며, 수강생은 총 N명이다. 지난 시간에 강의한 내용은 순열의 순서(Ranks of permutations)이다.

1부터 K까지 이루어진 수열이 있을 때, 각 숫자가 한 번씩만 등장하는 수열을 순열이라고 한다. 순열은 총 K!가지 경우의 수가 있을 수 있다. 수열 (1, 2, 3)은 총 3! = 6가지 방법으로 나타낼 수 있다. 순열은 첫 번째 숫자를 비교하고, 두 번째 숫자를 비교하고, ..., 이와 같은 방식으로 계속해서 비교하는 방식으로 순서를 매길 수 있다.

  1. (1, 2, 3)
  2. (1, 3, 2)
  3. (2, 1, 3)
  4. (2, 3, 1)
  5. (3, 1, 2)
  6. (3, 2, 1)

한 수열로 만들 수 있는 순열을 모두 순서대로 나열했을 때, 인덱스가 순열의 순서된다. 예를 들어, (3, 1, 2)의 순서는 5가 된다.

지승이는 학생들에게 순열의 순서를 계산하는 숙제를 내주려고 한다. 한 학생에게 순열을 하나 알려주고, 그 학생은 다음 수업 전까지 그 순열의 순서를 구해와야 한다.

지승이는 간단한 알고리즘을 이용해 숙제에 낼 순열을 만들려고 한다.

먼저, K개의 숫자로 이루어진 순열을 하나 아무거나 고른다. 그 다음, 학생마다 A와 B를 골라 A번째 수와 B번째 수의 위치를 바꾼 순열을 새롭게 만든다.

예를 들어, 고른 순열이 (1, 5, 4, 2, 3)이고, 고른 A와 B가 (1, 3), (2, 3), (2, 5)라면, 학생들이 받게되는 순열은 (4, 5, 1, 2, 3), (1, 4, 5, 2, 3), (1, 3, 4, 2, 5)가 된다. 각 순열의 순서는 91, 17, 9이다.

지승이가 고른 순열과 A와 B가 주어졌을 때, 각 순열의 순서를 구하는 프로그램을 작성하시오. 순서가 매우 커질 수 있기 때문에, 1,000,000,007로 나눈 나머지를 출력한다.

입력

첫째 줄에 K와 N이 주어진다. (2 ≤ K ≤ 300,000, 1 ≤ N ≤ 100,000) K는 순열의 길이, N은 학생의 수이다.

둘째 줄에는 지승이가 고른 순열이 주어진다. 순열은 1부터 K까지 정수 K개로 이루어져 있으며, 한 숫자는 한 번만 등장한다.

다음 N개 줄에는 A와 B가 주어진다. (1 ≤ A < B ≤ K)

출력

한 줄에 하나씩 순열의 순서를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

5 3
1 5 4 2 3
1 3
2 3
2 5

예제 출력 1

91
17
9

예제 입력 2

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

예제 출력 2

2
246045325
W3sicHJvYmxlbV9pZCI6IjMxMDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMWNcdWM1ZjRcdWM3NTggXHVjMjFjXHVjMTFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM5YzBcdWMyYjlcdWM3NzRcdWIyOTQgXHViMzAwXHVkNTU5XHVhZDUwXHVjNWQwXHVjMTFjIFx1YzIxOFx1ZDU1OVx1Yzc0NCBcdWFjMDBcdWI5NzRcdWNlNThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3NzRcdWJjODhcdWQ1NTlcdWFlMzBcdWM1ZDBcdWIyOTQgJnF1b3Q7XHVjNzc0XHVjMGIwIFx1YzIxOFx1ZDU1OVx1YWNmYyBcdWM4NzBcdWQ1NjlcdWI4NjAmcXVvdDtcdWM3NDQgXHVhYzAwXHViOTc0XHVjZTU4XHViYTcwLCBcdWMyMThcdWFjMTVcdWMwZGRcdWM3NDAgXHVjZDFkIE5cdWJhODVcdWM3NzRcdWIyZTQuIFx1YzljMFx1YjA5YyBcdWMyZGNcdWFjMDRcdWM1ZDAgXHVhYzE1XHVjNzU4XHVkNTVjIFx1YjBiNFx1YzZhOVx1Yzc0MCBcdWMyMWNcdWM1ZjRcdWM3NTggXHVjMjFjXHVjMTFjKFJhbmtzIG9mIHBlcm11dGF0aW9ucylcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjFcdWJkODBcdWQxMzAgS1x1YWU0Y1x1YzljMCBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0XHVjNzc0IFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIFx1YWMwMSBcdWMyMmJcdWM3OTBcdWFjMDAgXHVkNTVjIFx1YmM4OFx1YzUyOVx1YjljYyBcdWI0ZjFcdWM3YTVcdWQ1NThcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YzIxY1x1YzVmNFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzIxY1x1YzVmNFx1Yzc0MCBcdWNkMWQgSyFcdWFjMDBcdWM5YzAgXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjMjE4XHVjNWY0ICgxLCAyLCAzKVx1Yzc0MCBcdWNkMWQgMyEgPSA2XHVhYzAwXHVjOWMwIFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjMjFjXHVjNWY0XHVjNzQwIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViOTdjIFx1YmU0NFx1YWQ1MFx1ZDU1OFx1YWNlMCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWI5N2MgXHViZTQ0XHVhZDUwXHVkNTU4XHVhY2UwLCAuLi4sIFx1Yzc3NFx1YzY0MCBcdWFjMTlcdWM3NDAgXHViYzI5XHVjMmRkXHVjNzNjXHViODVjIFx1YWNjNFx1YzE4ZFx1ZDU3NFx1YzExYyBcdWJlNDRcdWFkNTBcdWQ1NThcdWIyOTQgXHViYzI5XHVjMmRkXHVjNzNjXHViODVjIFx1YzIxY1x1YzExY1x1Yjk3YyBcdWI5ZTRcdWFlMzggXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT4oMSwgMiwgMyk8XC9saT5cclxuXHQ8bGk+KDEsIDMsIDIpPFwvbGk+XHJcblx0PGxpPigyLCAxLCAzKTxcL2xpPlxyXG5cdDxsaT4oMiwgMywgMSk8XC9saT5cclxuXHQ8bGk+KDMsIDEsIDIpPFwvbGk+XHJcblx0PGxpPigzLCAyLCAxKTxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1ZDU1YyBcdWMyMThcdWM1ZjRcdWI4NWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMjFjXHVjNWY0XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViMDk4XHVjNWY0XHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVjNzc4XHViMzcxXHVjMmE0XHVhYzAwIFx1YzIxY1x1YzVmNFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWI0MWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsICgzLCAxLCAyKVx1Yzc1OCBcdWMyMWNcdWMxMWNcdWIyOTQgNVx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzljMFx1YzJiOVx1Yzc3NFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM1ZDBcdWFjOGMgXHVjMjFjXHVjNWY0XHVjNzU4IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWIyOTQgXHVjMjE5XHVjODFjXHViOTdjIFx1YjBiNFx1YzhmY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1ZDU1YyBcdWQ1NTlcdWMwZGRcdWM1ZDBcdWFjOGMgXHVjMjFjXHVjNWY0XHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWM1NGNcdWI4MjRcdWM4ZmNcdWFjZTAsIFx1YWRmOCBcdWQ1NTlcdWMwZGRcdWM3NDAgXHViMmU0XHVjNzRjIFx1YzIxOFx1YzVjNSBcdWM4MDRcdWFlNGNcdWM5YzAgXHVhZGY4IFx1YzIxY1x1YzVmNFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWI5N2MgXHVhZDZjXHVkNTc0XHVjNjQwXHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOWMwXHVjMmI5XHVjNzc0XHViMjk0IFx1YWMwNFx1YjJlOFx1ZDU1YyBcdWM1NGNcdWFjZTBcdWI5YWNcdWM5OThcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0IFx1YzIxOVx1YzgxY1x1YzVkMCBcdWIwYmMgXHVjMjFjXHVjNWY0XHVjNzQ0IFx1YjljY1x1YjRlNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmEzY1x1YzgwMCwgS1x1YWMxY1x1Yzc1OCBcdWMyMmJcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzIxY1x1YzVmNFx1Yzc0NCBcdWQ1NThcdWIwOTggXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1YWNlMFx1Yjk3OFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YywgXHVkNTU5XHVjMGRkXHViOWM4XHViMmU0IEFcdWM2NDAgQlx1Yjk3YyBcdWFjZThcdWI3N2MgQVx1YmM4OFx1YzlmOCBcdWMyMThcdWM2NDAgQlx1YmM4OFx1YzlmOCBcdWMyMThcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1YmMxNFx1YWZiYyBcdWMyMWNcdWM1ZjRcdWM3NDQgXHVjMGM4XHViODZkXHVhYzhjIFx1YjljY1x1YjRlMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVhY2UwXHViOTc4IFx1YzIxY1x1YzVmNFx1Yzc3NCAoMSwgNSwgNCwgMiwgMylcdWM3NzRcdWFjZTAsIFx1YWNlMFx1Yjk3OCBBXHVjNjQwIEJcdWFjMDAgKDEsIDMpLCAoMiwgMyksICgyLCA1KVx1Yjc3Y1x1YmE3NCwgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1YmMxYlx1YWM4Y1x1YjQxOFx1YjI5NCBcdWMyMWNcdWM1ZjRcdWM3NDAgKDQsIDUsIDEsIDIsIDMpLCAoMSwgNCwgNSwgMiwgMyksICgxLCAzLCA0LCAyLCA1KVx1YWMwMCBcdWI0MWNcdWIyZTQuIFx1YWMwMSBcdWMyMWNcdWM1ZjRcdWM3NTggXHVjMjFjXHVjMTFjXHViMjk0IDkxLCAxNywgOVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOWMwXHVjMmI5XHVjNzc0XHVhYzAwIFx1YWNlMFx1Yjk3OCBcdWMyMWNcdWM1ZjRcdWFjZmMgQVx1YzY0MCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWMwMSBcdWMyMWNcdWM1ZjRcdWM3NTggXHVjMjFjXHVjMTFjXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWMyMWNcdWMxMWNcdWFjMDAgXHViOWU0XHVjNmIwIFx1Y2VlNFx1YzljOCBcdWMyMTggXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgMSwwMDAsMDAwLDAwN1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgS1x1YzY0MCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBLICZsZTsgMzAwLDAwMCwgMSAmbGU7IE4gJmxlOyAxMDAsMDAwKSBLXHViMjk0IFx1YzIxY1x1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzQsIE5cdWM3NDAgXHVkNTU5XHVjMGRkXHVjNzU4Jm5ic3A7XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzljMFx1YzJiOVx1Yzc3NFx1YWMwMCBcdWFjZTBcdWI5NzggXHVjMjFjXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjMjFjXHVjNWY0XHVjNzQwIDFcdWJkODBcdWQxMzAgS1x1YWU0Y1x1YzljMCBcdWM4MTVcdWMyMTggS1x1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWQ1NWMgXHVjMjJiXHVjNzkwXHViMjk0IFx1ZDU1YyBcdWJjODhcdWI5Y2MgXHViNGYxXHVjN2E1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgQVx1YzY0MCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBBICZsdDsgQiAmbGU7IEspPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjMjFjXHVjNWY0XHVjNzU4IFx1YzIxY1x1YzExY1x1Yjk3YyAxLDAwMCwwMDAsMDA3XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMxMDMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBU0lTVEVOVCIsImRlc2NyaXB0aW9uIjoiPHA+UHJvZmVzc29yIERhbmtvIHRlYWNoZXMgbWF0aHMgYXQgdGhlIHVuaXZlcnNpdHkuIFRoaXMgc2VtZXN0ZXIgTiBzdHVkZW50cyBhdHRlbmQgaGlzIGxlY3R1cmVzIGluIGRpc2NyZXRlIG1hdGhlbWF0aWNzIGFuZCBjb21iaW5hdG9yaWNzLiBPbiBoaXMgbGFzdCBsZWN0dXJlIERhbmtvIHNwb2tlIGFib3V0IHJhbmtzIG9mIHBlcm11dGF0aW9ucy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QSBzZXF1ZW5jZSBvZiBLIGludGVnZXJzIGJldHdlZW4gMSBhbmQgSyBzdWNoIHRoYXQgZWFjaCBudW1iZXIgb2NjdXJzIGluIGEgc2VxdWVuY2UgZXhhY3RseSBvbmNlIGlzIGNhbGxlZCBhIHBlcm11dGF0aW9uLiBBIHBlcm11dGF0aW9uIGNhbiBiZSByZWFycmFuZ2VkIGludG8gdG90YWwgb2YgSyEgZGlmZmVyZW50IHNlcXVlbmNlcy4gRm9yIGV4YW1wbGUgYSBzZXF1ZW5jZSAoMSwgMiwgMykgY2FuIGJlIHJlYXJyYW5nZWQgaW4gMyEgPSA2IHdheXMuIFBlcm11dGF0aW9ucyBjYW4gYmUgb3JkZXJlZCBpbnRvIGEgc2VxdWVuY2Ugb2YgcGVybXV0YXRpb25zIGJ5IGNvbXBhcmluZyBmaXJzdCBlbGVtZW50cywgdGhhbiBzZWNvbmQgZWxlbWVudHMsIHRoZW4gdGhpcmQsIGFuZCBzbyBvbi4mbmJzcDs8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT4oMSwgMiwgMyk8XC9saT5cclxuXHQ8bGk+KDEsIDMsIDIpPFwvbGk+XHJcblx0PGxpPigyLCAxLCAzKTxcL2xpPlxyXG5cdDxsaT4oMiwgMywgMSk8XC9saT5cclxuXHQ8bGk+KDMsIDEsIDIpPFwvbGk+XHJcblx0PGxpPigzLCAyLCAxKTxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlRoZSBpbmRleCBvZiBhIHBlcm11dGF0aW9uIGluIGEgc2VxdWVuY2Ugb2YgcGVybXV0YXRpb25zIGlzIGNhbGxlZCB0aGUgcmFuayBvZiBwZXJtdXRhdGlvbi4gRm9yIGV4YW1wbGUsIHRoZSByYW5rIG9mIHBlcm11dGF0aW9uICgzLCAxLCAyKSBpcyA1LiZuYnNwOzxcL3A+XHJcblxyXG48cD5EYW5rbyBhc3NpZ25lZCBhIHBlcm11dGF0aW9uIHRvIGVhY2ggb2YgaGlzIHN0dWRlbnRzLiBFYWNoIHN0dWRlbnQgaGFzIHRvIGNhbGN1bGF0ZSB0aGUgcmFuayBvZiBnaXZlbiBwZXJtdXRhdGlvbi4gRGFua28gdXNlZCB0aGlzIHNpbXBsZSBhbGdvcml0aG0gdG8gZ2VuZXJhdGUgcGVybXV0YXRpb25zOiZuYnNwOzxcL3A+XHJcblxyXG48cD5IZSBwaWNrZWQgb25lIGJhc2UgcGVybXV0YXRpb24gb2YgSyBpbnRlZ2Vycy4gQSBwZXJtdXRhdGlvbiBmb3IgZWFjaCBvZiBoaXMgc3R1ZGVudCBpcyBvYnRhaW5lZCBmcm9tIGJhc2UgcGVybXV0YXRpb24gYnkgc3dhcHBpbmcgdHdvIGVsZW1lbnRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5EYW5rbyYjMzk7cyBhc3Npc3RhbnQgSmFua28gbXVzdCBnaXZlIGdyYWRlcyB0byBzdHVkZW50cy4gUHJvZmVzc29yIGdhdmUgaGltIHRoZSBiYXNlIHBlcm11dGF0aW9uIGFuZCBhIHNlcXVlbmNlIG9mIE4gcGFpcnMgb2YgaW5kaWNlcyB0aGF0IHNob3VsZCBiZSBzd2FwcGVkIHRvIG9idGFpbiBlYWNoIHBlcm11dGF0aW9uLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgaWYgdGhlIGJhc2UgcGVybXV0YXRpb24gd2VyZSAoMSwgNSwgNCwgMiwgMyksIGFuZCBwYWlycyBvZiBpbmRpY2VzIHdlcmUgKDEsIDMpLCAoMiwgMykgaSAoMiwgNSksIHRoZW4gc3R1ZGVudHMgZ290IHRoZXNlIHRocmVlIHBlcm11dGF0aW9uczogKDQsIDUsIDEsIDIsIDMpLCAoMSwgNCwgNSwgMiwgMykgaSAoMSwgMywgNCwgMiwgNSkuIFRoZSByYW5rcyBvZiBwZXJtdXRhdGlvbnMgYXJlIDkxLCAxNyBpIDksIHJlc3BlY3RpdmVseS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBoZWxwIEphbmtvIHRvIGNhbGN1bGF0ZSB0aGUgcmFua3Mgb2YgcGVybXV0YXRpb25zLiBUaGVzZSBudW1iZXJzIGNhbiBnZXQgdmVyeSBsYXJnZSwgc28gb3V0cHV0IHRoZSByZW1haW5kZXIgb2YgZGl2aXNpb24gYnkgMSAwMDAgMDAwIDAwNyBpbnN0ZWFkLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIEsgYW5kIE4gKDIgJmxlOyBLICZsZTsgMzAwIDAwMCwgMSAmbGU7IE4gJmxlOyAxMDAgMDAwKSwgdGhlIGxlbmd0aCBvZiB0aGUgYmFzZSBwZXJtdXRhdGlvbiBhbmQgdGhlIG51bWJlciBvZiBzdHVkZW50cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgbGluZSBjb250YWlucyB0aGUgYmFzZSBwZXJtdXRhdGlvbiAmbmRhc2g7IGEgc2VxdWVuY2Ugb2YgSyBpbnRlZ2VycyBiZXR3ZWVuIDEgYW5kIEsgc3VjaCB0aGF0IGVhY2ggbnVtYmVyIG9jY3VycyBpbiBhIHNlcXVlbmNlIGV4YWN0bHkgb25jZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgTiBsaW5lcyBjb250YWluIHR3byBpbnRlZ2VycyBlYWNoIEEgYW5kIEIgKDEgJmxlOyBBICZsdDsgQiAmbGU7IEspLCBpbmRpY2VzIG9mIHR3byBlbGVtZW50cyB0aGF0IHNob3VsZCBiZSBzd2FwcGVkIHRvIG9idGFpbiBlYWNoIHBlcm11dGF0aW9uLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBOIGludGVnZXJzLCBvbmUgcGVyIGxpbmUsIHRoZSByYW5rIG9mIGVhY2ggcGVybXV0YXRpb24gbW9kdWxvIDEgMDAwIDAwMCAwMDcgaW4gdGhlIG9yZGVyIHRoZXkgYXJlIHByZXNlbnRlZCBpbiB0aGUgaW5wdXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2010 > Final Exam #1 1번