Problem Statement
You will be given three integers N, M and K. You are to calculate the number of ways to place K rooks on a NxM chessboard in such a way that no rook is attacked by more than one other rook. A rook is attacked by another rook if they share a row or a column and there are no other rooks between them. To avoid problems with big numbers the calculation should be done modulo 1,000,001.
Definition
- Class:
- RooksPlacement
- Method:
- countPlacements
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int countPlacements(int N, int M, int K)
- (be sure your method is public)
Constraints
- N will be between 1 and 50, inclusive.
- M will be between 1 and 50, inclusive.
- K will be between 1 and 100, inclusive.
Examples
4
5
2
Returns: 190
There are only two rooks and therefore all placements are valid. The number of placements is (4 * 5) * (4 * 5 - 1) / 2 = 190.
2
3
3
Returns: 6
There are 6 possible placements: XX. X.X .XX ..X .X. X.. ..X .X. X.. XX. X.X .XX
6
7
20
Returns: 0
50
25
50
Returns: 879507
9
6
10
Returns: 340200
41
42
23
Returns: 333990
46
10
49
Returns: 0
40
1
7
Returns: 0
29
26
47
Returns: 0
3
46
25
Returns: 0
9
38
64
Returns: 0
5
5
49
Returns: 0
43
23
90
Returns: 0
18
29
86
Returns: 0
35
18
33
Returns: 695540
35
5
81
Returns: 0
4
9
24
Returns: 0
22
18
34
Returns: 0
49
10
90
Returns: 0
38
6
68
Returns: 0
7
6
70
Returns: 0
20
7
12
Returns: 318588
16
50
22
Returns: 627500
10
45
27
Returns: 0
36
9
88
Returns: 0
39
34
7
Returns: 62134
40
11
9
Returns: 129324
29
33
90
Returns: 0
41
17
51
Returns: 0
18
18
77
Returns: 0
35
28
94
Returns: 0
11
2
5
Returns: 0
23
37
39
Returns: 288688
23
35
61
Returns: 0
11
27
7
Returns: 814007
48
46
22
Returns: 888906
1
9
76
Returns: 0
13
29
69
Returns: 0
9
14
44
Returns: 0
15
8
79
Returns: 0
46
5
7
Returns: 359199
17
32
27
Returns: 328707
46
12
32
Returns: 0
43
34
52
Returns: 0
29
50
89
Returns: 0
18
23
15
Returns: 186506
3
47
5
Returns: 54372
28
33
5
Returns: 93658
20
37
43
Returns: 0
32
8
46
Returns: 0
21
3
49
Returns: 0
12
50
35
Returns: 0
42
14
48
Returns: 0
49
49
73
Returns: 0
8
28
77
Returns: 0
37
4
31
Returns: 0
30
21
61
Returns: 0
24
22
87
Returns: 0
11
27
97
Returns: 0
25
42
8
Returns: 207641
30
49
7
Returns: 979531
13
1
22
Returns: 0
2
43
99
Returns: 0
13
23
5
Returns: 7661
46
48
48
Returns: 43567
50
46
73
Returns: 0
50
47
46
Returns: 678182
45
47
56
Returns: 685248
47
47
19
Returns: 583709
49
48
43
Returns: 263494
50
45
37
Returns: 65849
48
46
40
Returns: 271023
45
46
99
Returns: 0
46
48
81
Returns: 0
45
50
8
Returns: 152867
47
50
80
Returns: 0
49
50
59
Returns: 83629
48
50
12
Returns: 929972
47
45
92
Returns: 0
49
48
28
Returns: 346171
47
48
85
Returns: 0
46
48
24
Returns: 50429
47
46
42
Returns: 245464
46
50
51
Returns: 882903
50
50
99
Returns: 0
50
50
100
Returns: 0
50
50
50
Returns: 344212
50
50
70
Returns: 0
1
1
2
Returns: 0
1
1
1
Returns: 1
1
2
2
Returns: 1
2
1
2
Returns: 1
2
1
1
Returns: 2
50
1
25
Returns: 0
50
2
51
Returns: 0
1
1
100
Returns: 0
50
50
1
Returns: 2500
50
50
2
Returns: 123747
50
50
3
Returns: 77407
50
50
66
Returns: 12772
50
50
67
Returns: 0
1
50
1
Returns: 50
50
1
2
Returns: 1225
1
50
3
Returns: 0
50
2
1
Returns: 100
2
50
2
Returns: 4950
50
2
3
Returns: 117600
2
50
4
Returns: 381799
50
2
5
Returns: 0
50
50
63
Returns: 404095
41
49
47
Returns: 878278
49
49
59
Returns: 636557
50
50
30
Returns: 894552
50
50
60
Returns: 613528
50
50
65
Returns: 872659
50
49
40
Returns: 14410