Problem Statement
Mr. Dengklek has a rectangular farm that can be represented with a grid that is divided into N rows and M columns (so there are N*M cells). He would like to place exactly one duck on each cell in the farm. Any such placement is called a duck formation. Some of the duck formations are beautiful. The beauty of a formation only depends on the duck types used in the formation: we say that two rows of a formation are similar if for each X between 1 and K, inclusive, they contain the same number of ducks of type X. A duck formation is beautiful if it does not contain any pair of similar rows. In other words, if there are two similar rows (not necessarily adjacent ones), the formation is not beautiful.
You are given the
Definition
- Class:
- DengklekCountingFormations
- Method:
- numFormations
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int numFormations(int N, int M, int K)
- (be sure your method is public)
Constraints
- N will be between 1 and 10, inclusive.
- M will be between 1 and 50, inclusive.
- K will be between 1 and 100, inclusive.
Examples
2
2
2
Returns: 10
These are the 10 beautiful duck formations: 1 1 1 1 1 1 1 2 1 2 1 2 2 1 2 2 1 1 2 2 2 1 2 1 2 2 2 2 2 2 1 1 2 2 1 1 1 2 2 1
1
1
58
Returns: 58
Mr. Dengklek can place a duck of any type in the single cell.
5
3
2
Returns: 0
3
5
7
Returns: 894953467
7
47
74
Returns: 778075142
1
1
1
Returns: 1
10
50
100
Returns: 882217320
2
2
2
Returns: 10
3
9
74
Returns: 322572571
8
2
31
Returns: 448167988
2
35
11
Returns: 827591288
10
41
100
Returns: 499576513
3
18
13
Returns: 940249024
7
3
10
Returns: 201256387
10
39
81
Returns: 309707622
6
35
28
Returns: 209574503
6
23
2
Returns: 312684759
7
34
53
Returns: 178470265
8
8
13
Returns: 222147990
4
36
16
Returns: 582314457
4
9
3
Returns: 938598903
6
28
93
Returns: 638399990
6
22
62
Returns: 780094411
8
50
14
Returns: 951067372
7
19
54
Returns: 576972993
10
46
88
Returns: 899882197
7
22
11
Returns: 626867463
1
40
46
Returns: 498142982
5
10
4
Returns: 694451690
8
3
91
Returns: 855332855
5
28
99
Returns: 906532409
9
14
28
Returns: 82041125
1
49
52
Returns: 141753950
2
48
51
Returns: 34133860
8
6
72
Returns: 979683844
1
45
69
Returns: 475746964
9
14
90
Returns: 457723292
9
34
82
Returns: 366327521
6
8
41
Returns: 321494072
9
47
93
Returns: 192075956
1
4
20
Returns: 160000
1
12
85
Returns: 826157272
9
13
83
Returns: 912915695
2
26
82
Returns: 814639292
2
3
40
Returns: 95630212
5
36
36
Returns: 115379814
4
4
99
Returns: 175968595
5
34
82
Returns: 237392719
6
11
42
Returns: 297426881
6
40
38
Returns: 263330620
10
12
91
Returns: 388184928
2
33
3
Returns: 742311074
6
33
17
Returns: 50118480
1
34
94
Returns: 862227104
4
37
97
Returns: 774321359
3
12
34
Returns: 879192519
1
7
89
Returns: 334585912