Problem Statement
One day, the queen of the kingdom challenged Mr. Dengklek with a perplexing puzzle: she gave Mr. Dengklek an N × M board made of wood that consists of N*M squares. She then asked Mr. Dengklek to paint the squares according to these rules:
- Each square must be either colored or empty.
- Each colored square must have an even number of adjacent colored squares. Two squares are adjacent if they share a side.
In the above image, black squares denote empty squares and brown squares denote colored squares.
Of course, finding one solution to the puzzle is easy: we do not color anything. Instead, the queen asked Mr. Dengklek a much harder question: to count all valid solutions of the puzzle. Help Mr. Dengklek count the solutions and return the result modulo 1,000,000,007. Two solutions are different if there is a square that is colored in one solution and not colored in the other solution.
Definition
- Class:
- DengklekPaintingSquares
- Method:
- numSolutions
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int numSolutions(int N, int M)
- (be sure your method is public)
Constraints
- N will be between 1 and 100, inclusive.
- M will be between 1 and 8, inclusive.
Examples
1
1
Returns: 2
Either Mr. Dengklek colors the square, or he does not. Both choices produce a valid solution.
2
2
Returns: 8
Here are the 8 valid solutions:
1
3
Returns: 5
47
7
Returns: 944149920
1
2
Returns: 3
1
4
Returns: 8
1
5
Returns: 13
1
6
Returns: 21
1
7
Returns: 34
1
8
Returns: 55
3
5
Returns: 1067
4
2
Returns: 48
6
7
Returns: 142860055
7
6
Returns: 142860055
10
6
Returns: 852065842
10
7
Returns: 133047026
12
4
Returns: 217922751
12
6
Returns: 551648439
12
7
Returns: 509252402
15
4
Returns: 867152507
16
8
Returns: 559575281
17
4
Returns: 504929571
20
3
Returns: 133418092
21
6
Returns: 154558076
23
8
Returns: 238358301
25
1
Returns: 196418
25
6
Returns: 417472647
31
1
Returns: 3524578
32
8
Returns: 452099666
33
2
Returns: 434804009
33
4
Returns: 360549211
34
7
Returns: 892665396
36
5
Returns: 117112746
36
7
Returns: 665050769
36
8
Returns: 778391605
37
3
Returns: 22962921
38
1
Returns: 102334155
40
2
Returns: 696374975
41
5
Returns: 278606644
44
2
Returns: 746383206
45
2
Returns: 772345493
45
3
Returns: 814257636
47
2
Returns: 759037600
47
6
Returns: 388356121
48
3
Returns: 100797928
49
3
Returns: 796812565
49
8
Returns: 490790721
51
3
Returns: 806147414
56
5
Returns: 359935014
57
2
Returns: 422144489
57
7
Returns: 305868052
58
3
Returns: 919543957
64
3
Returns: 726998433
71
1
Returns: 527403788
75
3
Returns: 45508041
75
5
Returns: 697209289
77
2
Returns: 985695704
77
3
Returns: 458872362
77
4
Returns: 689857849
81
1
Returns: 400391533
81
8
Returns: 63610655
86
1
Returns: 665487541
86
3
Returns: 126082288
87
7
Returns: 589627493
88
8
Returns: 330398667
89
6
Returns: 643421135
90
2
Returns: 497304262
91
4
Returns: 726399354
91
7
Returns: 352147883
93
5
Returns: 368736803
93
7
Returns: 897180692
95
4
Returns: 662160581
98
2
Returns: 166674494
98
8
Returns: 536977998
99
7
Returns: 551738264
100
1
Returns: 470199269
100
2
Returns: 398139603
100
3
Returns: 76803773
100
4
Returns: 393669896
100
5
Returns: 804089593
100
6
Returns: 545306804
100
7
Returns: 124439073
100
8
Returns: 636302453
99
8
Returns: 857844889