시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2 2 2 100.000%

문제

상근이는 n개의 전구와 스위치 n개를 가지고 있다. 각 전구는 켜져있거나 꺼져있고, 스위치는 각 전구에 연결되어 있다. 스위치는 전구의 상태를 반대로 바꾼다. 즉, 켜져있는 전구의 스위치를 누르면 전구를 끄고, 반대의 경우에는 반대로 행동한다. 상근이는 이 전구를 가지고 하는 게임을 만들었다.

전구는 스위치의 조합을 선택하고, 그 스위치를 누르는 것이 한 턴이다. 스위치를 전혀 선택하지 않는 경우도 가능한 스위치의 조합이다. m턴이 지난 후에 처음 v개 전구는 켜져있는 상태, 나머지는 꺼져있는 상태가 되어야 한다. 이 게임에는 제약이 하나 있는데, 한 조합을 두 번 이상 사용할 수 없다.

이 게임은 매우 쉬운 게임이기 때문에 이기는 방법이 매우 많다. 상근이는 이기는 방법을 모두 찾으려고 한다. 총 몇 가지 경우가 있는지 구하는 프로그램을 작성하시오.

게임을 이기는 두 방법 A와 B가 있을 때, 방법 A의 순서를 적절히 바꿔서 다른 방법 B를 만들 수 있다면, 같은 방법이다.

예를 들어, n=4, m=3, v=2인 경우에, 첫 턴에 1, 2, 4를, 둘째 턴에 1, 3을 셋째 턴에 1, 3, 4를 누르면 게임을 이길 수 있다. 이 방법은 첫 턴에 1, 3을 누르고, 둘째 턴에 1, 2, 4, 셋째 턴에 1, 3, 4를 누르는 방법과 동일하다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있고, 500개를 넘지 않는다. 각 테스트 케이스는 한 줄로 이루어져 있고, n (1 ≤ n ≤ 1,000), m (1 ≤ m ≤ 1,000), v (0 ≤ v ≤ n)이 주어진다. 마지막 줄에는 0 0 0이 주어진다.

출력

각 테스트 케이스에 대해서 게임을 이기는 방법의 수를 10567201로 나눈 나머지를 출력한다.

예제 입력 1

3 3 1
6 4 0
6 4 3
0 0 0

예제 출력 1

7
10416
9920
W3sicHJvYmxlbV9pZCI6IjM4NTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MDRcdWFkNmMgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgblx1YWMxY1x1Yzc1OCBcdWM4MDRcdWFkNmNcdWM2NDAgXHVjMmE0XHVjNzA0XHVjZTU4IG5cdWFjMWNcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YzgwNFx1YWQ2Y1x1YjI5NCBcdWNmMWNcdWM4MzhcdWM3ODhcdWFjNzBcdWIwOTggXHVhZWJjXHVjODM4XHVjNzg4XHVhY2UwLCBcdWMyYTRcdWM3MDRcdWNlNThcdWIyOTQgXHVhYzAxIFx1YzgwNFx1YWQ2Y1x1YzVkMCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWMyYTRcdWM3MDRcdWNlNThcdWIyOTQgXHVjODA0XHVhZDZjXHVjNzU4IFx1YzBjMVx1ZDBkY1x1Yjk3YyBcdWJjMThcdWIzMDBcdWI4NWMgXHViYzE0XHVhZmJjXHViMmU0LiBcdWM5ODksIFx1Y2YxY1x1YzgzOFx1Yzc4OFx1YjI5NCBcdWM4MDRcdWFkNmNcdWM3NTggXHVjMmE0XHVjNzA0XHVjZTU4XHViOTdjIFx1YjIwNFx1Yjk3NFx1YmE3NCBcdWM4MDRcdWFkNmNcdWI5N2MgXHViMDQ0XHVhY2UwLCBcdWJjMThcdWIzMDBcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YmMxOFx1YjMwMFx1Yjg1YyBcdWQ1ODlcdWIzZDlcdWQ1NWNcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3NzQgXHVjODA0XHVhZDZjXHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWQ1NThcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YjljY1x1YjRlNFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODA0XHVhZDZjXHViMjk0IFx1YzJhNFx1YzcwNFx1Y2U1OFx1Yzc1OCBcdWM4NzBcdWQ1NjlcdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTU4XHVhY2UwLCBcdWFkZjggXHVjMmE0XHVjNzA0XHVjZTU4XHViOTdjIFx1YjIwNFx1Yjk3NFx1YjI5NCBcdWFjODNcdWM3NzQgXHVkNTVjIFx1ZDEzNFx1Yzc3NFx1YjJlNC4gXHVjMmE0XHVjNzA0XHVjZTU4XHViOTdjIFx1YzgwNFx1ZDYwMCBcdWMxMjBcdWQwZGRcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YWNiZFx1YzZiMFx1YjNjNCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjMmE0XHVjNzA0XHVjZTU4XHVjNzU4IFx1Yzg3MFx1ZDU2OVx1Yzc3NFx1YjJlNC4gbVx1ZDEzNFx1Yzc3NCBcdWM5YzBcdWIwOWMgXHVkNmM0XHVjNWQwIFx1Y2M5OFx1Yzc0YyB2XHVhYzFjIFx1YzgwNFx1YWQ2Y1x1YjI5NCBcdWNmMWNcdWM4MzhcdWM3ODhcdWIyOTQgXHVjMGMxXHVkMGRjLCBcdWIwOThcdWJhMzhcdWM5YzBcdWIyOTQgXHVhZWJjXHVjODM4XHVjNzg4XHViMjk0IFx1YzBjMVx1ZDBkY1x1YWMwMCBcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNWQwXHViMjk0IFx1YzgxY1x1YzU3ZFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjNzg4XHViMjk0XHViMzcwLCBcdWQ1NWMgXHVjODcwXHVkNTY5XHVjNzQ0IFx1YjQ1MCBcdWJjODggXHVjNzc0XHVjMGMxIFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQwIFx1YjllNFx1YzZiMCBcdWMyNmNcdWM2YjQgXHVhYzhjXHVjNzg0XHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM3NzRcdWFlMzBcdWIyOTQgXHViYzI5XHViYzk1XHVjNzc0IFx1YjllNFx1YzZiMCBcdWI5Y2VcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3NzRcdWFlMzBcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWNjM2VcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWNkMWQgXHViYTg3IFx1YWMwMFx1YzljMCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWFjOGNcdWM3ODRcdWM3NDQgXHVjNzc0XHVhZTMwXHViMjk0IFx1YjQ1MCBcdWJjMjlcdWJjOTUgQVx1YzY0MCBCXHVhYzAwIFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIFx1YmMyOVx1YmM5NSBBXHVjNzU4IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWM4MDFcdWM4MDhcdWQ3ODggXHViYzE0XHVhZmQ0XHVjMTFjIFx1YjJlNFx1Yjk3OCBcdWJjMjlcdWJjOTUgQlx1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YmE3NCwgXHVhYzE5XHVjNzQwIFx1YmMyOVx1YmM5NVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgbj00LCBtPTMsIHY9Mlx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDAsIFx1Y2NhYiBcdWQxMzRcdWM1ZDAgMSwgMiwgNFx1Yjk3YywgXHViNDU4XHVjOWY4IFx1ZDEzNFx1YzVkMCAxLCAzXHVjNzQ0IFx1YzE0Ylx1YzlmOCBcdWQxMzRcdWM1ZDAgMSwgMywgNFx1Yjk3YyBcdWIyMDRcdWI5NzRcdWJhNzQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1Yzc3NFx1YWUzOCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViYzI5XHViYzk1XHVjNzQwIFx1Y2NhYiBcdWQxMzRcdWM1ZDAgMSwgM1x1Yzc0NCBcdWIyMDRcdWI5NzRcdWFjZTAsIFx1YjQ1OFx1YzlmOCBcdWQxMzRcdWM1ZDAgMSwgMiwgNCwgXHVjMTRiXHVjOWY4IFx1ZDEzNFx1YzVkMCAxLCAzLCA0XHViOTdjIFx1YjIwNFx1Yjk3NFx1YjI5NCBcdWJjMjlcdWJjOTVcdWFjZmMgXHViM2Q5XHVjNzdjXHVkNTU4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCA1MDBcdWFjMWNcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBuICgxICZsZTsgbiAmbGU7IDEsMDAwKSwgbSAoMSAmbGU7IG0gJmxlOyAxLDAwMCksIHYgKDAgJmxlOyB2ICZsZTsgbilcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDAgMCAwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1Yzc3NFx1YWUzMFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIDEwNTY3MjAxXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM4NTciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMaWdodHMiLCJkZXNjcmlwdGlvbiI6IjxwPkpvaG4gaGFzIG4gbGlnaHQgYnVsYnMgYW5kIGEgc3dpdGNoYm9hcmQgd2l0aCBuIHN3aXRjaGVzOyBlYWNoIGJ1bGIgY2FuIGJlIGVpdGhlciBvbiBvciBvZmYsIGFuZCBwcmVzc2luZyB0aGUgaXRoIHN3aXRjaCBjaGFuZ2VzIHRoZSBzdGF0ZSBvZiBidWxiIGkgZnJvbSBvbiB0byBvZmYsIGFuZCB2aWNldmVyc2EuIEhlIGlzIHVzaW5nIHRoZW0gdG8gcGxheSBhIGdhbWUgaGUgaGFzIG1hZGUgdXAuIEluIGVhY2ggbW92ZSwgSm9obiBzZWxlY3RzIGEgKHBvc3NpYmx5IGVtcHR5KSBzZXQgb2Ygc3dpdGNoZXMgYW5kIHByZXNzZXMgdGhlbSwgdGh1cyBpbnZlcnRpbmcgdGhlIHN0YXRlcyBvZiB0aGUgY29ycmVzcG9uZGluZyBidWxicy4gQWZ0ZXIgZXhhY3RseSBtIG1vdmVzLCBKb2huIHdvdWxkIGxpa2UgdG8gaGF2ZSB0aGUgZmlyc3QgdiBidWxicyBvbiBhbmQgdGhlIHJlc3Qgb2ZmOyBvdGhlcndpc2UgaGUgbG9zZXMgdGhlIGdhbWUuIFRoZXJlIGlzIG9ubHkgb25lIHJlc3RyaWN0aW9uOiBoZSBpcyBub3QgYWxsb3dlZCB0byBwcmVzcyB0aGUgc2FtZSBzZXQgb2Ygc3dpdGNoZXMgaW4gdHdvIGRpIGVyZW50IG1vdmVzLjxcL3A+XHJcblxyXG48cD5UaGlzIGlzIHF1aXRlIGFuIGVhc3kgZ2FtZSwgYXMgdGhlcmUgYXJlIGxvdHMgb2Ygd2F5cyBvZiB3aW5uaW5nLiBUaGlzIGhhcyBlbmNvdXJhZ2VkIGhpbSB0byBrZWVwIHBsYXlpbmcgZGlmZmVyZW50IHdpbm5pbmcgZ2FtZXMsIGFuZCBub3cgaGUgaXMgaW50ZW50IG9uIHRyeWluZyB0aGVtIGFsbC4gSGVscCBoaW0gY291bnQgaG93IG1hbnkgd2F5cyBvZiB3aW5uaW5nIHRoZXJlIGFyZS4gVHdvIGdhbWVzIGFyZSBjb25zaWRlcmVkIHRoZSBzYW1lIGlmLCBhZnRlciBhIHJlb3JkZXJpbmcgb2YgdGhlIG1vdmVzIGluIG9uZSBvZiB0aGVtLCBhdCBldmVyeSBzdGVwIHRoZSBzYW1lIHNldCBvZiBzd2l0Y2hlcyBpcyBwcmVzc2VkIGluIGJvdGggb2YgdGhlbS48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGlmIG4gPSA0LCBtID0gMywgYW5kIHYgPSAyLCBvbmUgcG9zc2libGUgd2lubmluZyBnYW1lIGlzIG9idGFpbmVkIGJ5IHByZXNzaW5nIHN3aXRjaGVzIDEsIDIgYW5kIDQgaW4gdGhlIGZpcnN0IG1vdmUsIDEgYW5kIDMgaW4gdGhlIHNlY29uZCBvbmUsIGFuZCAxLCAzIGFuZCA0IGluIHRoZSBsYXN0IG9uZS4gVGhpcyBpcyBjb25zaWRlcmVkIGVxdWl2YWxlbnQgdG8sIHNheSwgZmlyc3QgcHJlc3NpbmcgMSBhbmQgMzsgdGhlbiAxLCAyLCA0OyBhbmQgdGhlbiAxLCAzLCA0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGhhcyBhdCBtb3N0IDUwMCBsaW5lcywgb25lIGZvciBlYWNoIHRlc3QgY2FzZS4gRWFjaCBsaW5lIGNvbnRhaW5zIHRocmVlIGludGVnZXJzIG4gKDEgJmxlOyBuICZsZTsgMSAwMDApLCBtICgxICZsZTsgbSAmbGU7IDEgMDAwKSwgYW5kIHYgKDAgJmxlOyB2ICZsZTsgbikuIFRoZSBsYXN0IGxpbmUgb2YgaW5wdXQgd2lsbCBob2xkIHRoZSB2YWx1ZXMgMCAwIDAgYW5kIG11c3Qgbm90IGJlIHByb2Nlc3NlZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCBvbmUgbGluZSBmb3IgZWFjaCB0ZXN0IGNhc2UgY29udGFpbmluZyB0aGUgbnVtYmVyIG9mIHdheXMgSm9obiBjYW4gcGxheSB0aGUgZ2FtZSwgbW9kdWxvIHRoZSBwcmltZSAxMCA1NjcgMjAxLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==