시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzg1NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkxpZ2h0cyIsImRlc2NyaXB0aW9uIjoiPHA+Sm9obiBoYXMgbiBsaWdodCBidWxicyBhbmQgYSBzd2l0Y2hib2FyZCB3aXRoIG4gc3dpdGNoZXM7IGVhY2ggYnVsYiBjYW4gYmUgZWl0aGVyIG9uIG9yIG9mZiwgYW5kIHByZXNzaW5nIHRoZSBpdGggc3dpdGNoIGNoYW5nZXMgdGhlIHN0YXRlIG9mIGJ1bGIgaSBmcm9tIG9uIHRvIG9mZiwgYW5kIHZpY2V2ZXJzYS4gSGUgaXMgdXNpbmcgdGhlbSB0byBwbGF5IGEgZ2FtZSBoZSBoYXMgbWFkZSB1cC4gSW4gZWFjaCBtb3ZlLCBKb2huIHNlbGVjdHMgYSAocG9zc2libHkgZW1wdHkpIHNldCBvZiBzd2l0Y2hlcyBhbmQgcHJlc3NlcyB0aGVtLCB0aHVzIGludmVydGluZyB0aGUgc3RhdGVzIG9mIHRoZSBjb3JyZXNwb25kaW5nIGJ1bGJzLiBBZnRlciBleGFjdGx5IG0gbW92ZXMsIEpvaG4gd291bGQgbGlrZSB0byBoYXZlIHRoZSBmaXJzdCB2IGJ1bGJzIG9uIGFuZCB0aGUgcmVzdCBvZmY7IG90aGVyd2lzZSBoZSBsb3NlcyB0aGUgZ2FtZS4gVGhlcmUgaXMgb25seSBvbmUgcmVzdHJpY3Rpb246IGhlIGlzIG5vdCBhbGxvd2VkIHRvIHByZXNzIHRoZSBzYW1lIHNldCBvZiBzd2l0Y2hlcyBpbiB0d28gZGkgZXJlbnQgbW92ZXMuPFwvcD5cclxuXHJcbjxwPlRoaXMgaXMgcXVpdGUgYW4gZWFzeSBnYW1lLCBhcyB0aGVyZSBhcmUgbG90cyBvZiB3YXlzIG9mIHdpbm5pbmcuIFRoaXMgaGFzIGVuY291cmFnZWQgaGltIHRvIGtlZXAgcGxheWluZyBkaWZmZXJlbnQgd2lubmluZyBnYW1lcywgYW5kIG5vdyBoZSBpcyBpbnRlbnQgb24gdHJ5aW5nIHRoZW0gYWxsLiBIZWxwIGhpbSBjb3VudCBob3cgbWFueSB3YXlzIG9mIHdpbm5pbmcgdGhlcmUgYXJlLiBUd28gZ2FtZXMgYXJlIGNvbnNpZGVyZWQgdGhlIHNhbWUgaWYsIGFmdGVyIGEgcmVvcmRlcmluZyBvZiB0aGUgbW92ZXMgaW4gb25lIG9mIHRoZW0sIGF0IGV2ZXJ5IHN0ZXAgdGhlIHNhbWUgc2V0IG9mIHN3aXRjaGVzIGlzIHByZXNzZWQgaW4gYm90aCBvZiB0aGVtLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgaWYgbiA9IDQsIG0gPSAzLCBhbmQgdiA9IDIsIG9uZSBwb3NzaWJsZSB3aW5uaW5nIGdhbWUgaXMgb2J0YWluZWQgYnkgcHJlc3Npbmcgc3dpdGNoZXMgMSwgMiBhbmQgNCBpbiB0aGUgZmlyc3QgbW92ZSwgMSBhbmQgMyBpbiB0aGUgc2Vjb25kIG9uZSwgYW5kIDEsIDMgYW5kIDQgaW4gdGhlIGxhc3Qgb25lLiBUaGlzIGlzIGNvbnNpZGVyZWQgZXF1aXZhbGVudCB0bywgc2F5LCBmaXJzdCBwcmVzc2luZyAxIGFuZCAzOyB0aGVuIDEsIDIsIDQ7IGFuZCB0aGVuIDEsIDMsIDQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgaGFzIGF0IG1vc3QgNTAwIGxpbmVzLCBvbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBFYWNoIGxpbmUgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgbiAoMSAmbGU7IG4gJmxlOyAxIDAwMCksIG0gKDEgJmxlOyBtICZsZTsgMSAwMDApLCBhbmQgdiAoMCAmbGU7IHYgJmxlOyBuKS4gVGhlIGxhc3QgbGluZSBvZiBpbnB1dCB3aWxsIGhvbGQgdGhlIHZhbHVlcyAwIDAgMCBhbmQgbXVzdCBub3QgYmUgcHJvY2Vzc2VkLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZSBjb250YWluaW5nIHRoZSBudW1iZXIgb2Ygd2F5cyBKb2huIGNhbiBwbGF5IHRoZSBnYW1lLCBtb2R1bG8gdGhlIHByaW1lIDEwIDU2NyAyMDEuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=