Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!
Language:
Lights
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 214Accepted: 86

Description

John has n light bulbs and a switchboard with n switches; each bulb can be either on or off, and pressing the i-th switch changes the state of bulb i from on to off, and viceversa. He is using them to play a game he has made up. In each move, John selects a (possibly empty) set of switches and presses them, thus inverting the states of the corresponding bulbs. After exactly m moves, John would like to have the first v bulbs on and the rest off; otherwise he loses the game. There is only one restriction: he is not allowed to press the same set of switches in two different moves.
This is quite an easy game, as there are lots of ways of winning. This has encouraged him to keep playing different winning games, and now he is intent on trying them all. Help him count how many ways of winning there are. Two games are considered the same if, after a reordering of the moves in one of them, at every step the same set of switches is pressed in both of them.
For example, if n = 4, m = 3, and v = 2, one possible winning game is obtained by pressing switches 1, 2 and 4 in the first move, 1 and 3 in the second one, and 1, 3 and 4 in the last one. This is considered equivalent to, say, first pressing 1 and 3; then 1, 2, 4; and then 1, 3, 4.

Input

The input has at most 500 lines, one for each test case. Each line contains three integers n (1 <= n <= 1 000), m (1 <= m <= 1 000), and v (0 <= v <= n). The last line of input will hold the values 0 0 0 and must not be processed.

Output

Print one line for each test case containing the number of ways John can play the game, modulo the prime 10 567 201.

Sample Input

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

Sample Output

7
10416
9920

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator