Problem Statement
There is a grid with H rows and W columns. All cells in the grid are initially white.
You may perform zero or more painting steps. Each step looks as follows:
- You select either any one column of the grid, or any one diagonal that goes down and to the right.
- You paint all its cells black.
The same cell can be painted multiple times. Once it's black, it remains black when you paint it again.
Two grids are different if one of them has a white cell at some coordinates at which the other grid has a black cell. Compute and return the number of different grids you can obtain, modulo 1,000,000,007.
Definition
- Class:
- DiagonalColumn
- Method:
- countGrids
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int countGrids(int H, int W)
- (be sure your method is public)
Constraints
- H and W will be between 1 and 38, inclusive.
Examples
2
2
Returns: 12
In the figure below, the columns and diagonals you are allowed to paint are shown using asterisks. columns: diagonals: *. .* .. *. .* *. .* *. .* .. The 12 different grids that can be produced are shown below, using '.' for white and '#' for black. .. .. .# #. .. #. .. #. #. .# .# ## .# .# #. #. ## .# #. ## .# ## ## ## And the four grids that cannot be produced look as follows: #. .. ## .. .. .# .. ##
2
3
Returns: 37
3
2
Returns: 28
1
5
Returns: 32
Each of the 2^5 black-and-white grids can be produced.
6
1
Returns: 64
38
38
Returns: 173889321
1
1
Returns: 2
1
2
Returns: 4
2
1
Returns: 4
1
38
Returns: 877905026
38
1
Returns: 877905026
1
35
Returns: 359738130
2
4
Returns: 114
5
2
Returns: 124
3
3
Returns: 97
7
7
Returns: 455383
8
3
Returns: 3817
4
15
Returns: 23475582
20
7
Returns: 819951426
1
5
Returns: 32
1
12
Returns: 4096
1
21
Returns: 2097152
2
4
Returns: 114
9
38
Returns: 842071268
10
7
Returns: 3719511
11
9
Returns: 119096740
11
38
Returns: 867883277
12
20
Returns: 848104343
14
27
Returns: 868261569
18
25
Returns: 105113581
20
10
Returns: 338245748
23
22
Returns: 97737204
25
35
Returns: 825569109
27
38
Returns: 664024083
28
37
Returns: 368521022
29
2
Returns: 147483630
30
1
Returns: 73741817
30
11
Returns: 604592928
30
38
Returns: 686026055
32
4
Returns: 108101312
32
6
Returns: 10144107
32
15
Returns: 200632290
32
24
Returns: 453202823
32
38
Returns: 455885098
33
37
Returns: 766433769
33
38
Returns: 967662257
34
20
Returns: 433610898
34
36
Returns: 260621441
34
37
Returns: 891986731
34
38
Returns: 909977075
35
35
Returns: 245969105
35
36
Returns: 376478799
35
37
Returns: 219074228
35
38
Returns: 30111373
36
34
Returns: 952378827
36
35
Returns: 972723436
36
36
Returns: 52399766
36
37
Returns: 522725515
36
38
Returns: 247302652
37
33
Returns: 205358595
37
34
Returns: 751435092
37
35
Returns: 426232084
37
36
Returns: 404241707
37
37
Returns: 748424347
37
38
Returns: 170589035
38
30
Returns: 274152123
38
32
Returns: 459360570
38
33
Returns: 116506807
38
34
Returns: 349547622
38
35
Returns: 333249387
38
36
Returns: 107925582
38
37
Returns: 199822004
38
38
Returns: 173889321
37
29
Returns: 971826486
25
36
Returns: 416841565
9
10
Returns: 118374176