Problem Statement
This problem is about bitmaps. All bitmaps in this problem are black-and-white bitmaps with R rows and C columns.
A bitmap is called a checkerboard if it has the property that no two pixels that share a side share the same color: each black pixel must be horizontally and vertically adjacent to only white pixels and vice versa. Clearly, for any dimensions R and C there are exactly two distinct checkerboards.
The checkerboard distance of a bitmap is the minimum number of pixels that have to be edited (i.e., turned from black to white or vice versa) in order to change that bitmap into a checkerboard.
For example, the bitmap shown below (using 'W' and 'B' for white and black pixels) has checkerboard distance 2.
WBWBW BWBWB BBWWW BWBWB
You are given the dimensions R and C and the checkerboard distance D. Count all bitmaps with these parameters, and return that count modulo 10^9 + 7.
Definition
- Class:
- AlmostCheckerboards
- Method:
- count
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int count(int R, int C, int D)
- (be sure your method is public)
Constraints
- R will be between 1 and 100, inclusive.
- C will be between 1 and 100, inclusive.
- D will be between 0 and 100, inclusive.
Examples
3
4
0
Returns: 2
The two perfect checkerboards are shown below: BWBW WBWB WBWB BWBW BWBW WBWB
3
4
47
Returns: 0
You can transform any 3x4 bitmap into any other 3x4 bitmap in at most 3x4 = 12 changes, so there clearly won't be any bitmaps with checkerboard distance exactly equal to 47.
2
2
1
Returns: 8
The eight bitmaps that match these parameters are precisely all the bitmaps that contains three pixels of one color and one pixel of the opposite color. The edit that turns it into a valid checkerboard is always to find the pixel that has the unique color and to toggle the pixel that is diagonally opposite it to make it match.
9
4
15
Returns: 135805043
Remember that the answer should be computed modulo 10^9 + 7. (The exact answer for this test case is 11,135,805,120, and that modulo 1,000,000,007 is 135,805,043.)
2
2
2
Returns: 6
100
100
100
Returns: 277296858
5
2
38
Returns: 0
5
4
2
Returns: 380
66
15
59
Returns: 174298992
7
6
68
Returns: 0
3
2
1
Returns: 12
63
44
71
Returns: 562679624
3
3
2
Returns: 72
8
1
3
Returns: 112
6
1
44
Returns: 0
1
1
0
Returns: 2
17
20
69
Returns: 481883412
9
20
71
Returns: 51013034
4
2
0
Returns: 2
4
4
3
Returns: 1120
77
18
8
Returns: 938953264
10
3
15
Returns: 155117520
3
3
4
Returns: 252
4
3
1
Returns: 24
16
17
58
Returns: 218235347
6
2
11
Returns: 0
14
3
11
Returns: 561122696
38
1
19
Returns: 345263555
6
24
72
Returns: 922252734
11
2
13
Returns: 0
9
4
86
Returns: 0
16
11
2
Returns: 30800
2
2
0
Returns: 2
33
6
99
Returns: 690285631
8
6
86
Returns: 0
4
4
5
Returns: 8736
3
1
0
Returns: 2
71
40
30
Returns: 440629954
6
16
12
Returns: 300317601
12
39
6
Returns: 686267341
1
4
3
Returns: 0
20
70
43
Returns: 926106478
2
2
2
Returns: 6
4
2
4
Returns: 70
5
7
98
Returns: 0
4
8
84
Returns: 0
12
1
6
Returns: 924
65
15
96
Returns: 645862819
4
4
7
Returns: 22880
3
1
2
Returns: 0
2
4
2
Returns: 56
5
8
99
Returns: 0
20
71
74
Returns: 603443841
11
9
87
Returns: 0
4
4
0
Returns: 2
19
10
95
Returns: 900580233
4
4
9
Returns: 0
3
3
1
Returns: 18
8
8
35
Returns: 0
56
73
66
Returns: 376136511
1
34
17
Returns: 333606206
14
12
84
Returns: 964149357
17
16
25
Returns: 564860399
7
15
26
Returns: 647437726
38
4
76
Returns: 427263280
13
2
66
Returns: 0
11
4
93
Returns: 0
10
12
54
Returns: 765272133
19
8
27
Returns: 245363747
46
4
92
Returns: 950548968
2
1
1
Returns: 2
32
6
96
Returns: 896058825
4
4
2
Returns: 240
17
8
14
Returns: 832162014
49
16
2
Returns: 613872
11
13
34
Returns: 728039017
1
4
0
Returns: 2
3
3
3
Returns: 168
98
35
79
Returns: 86767211
1
3
74
Returns: 0
2
20
8
Returns: 153809370
89
10
22
Returns: 709057260
7
13
31
Returns: 956306082
74
11
72
Returns: 656062277
37
91
62
Returns: 196322604
12
12
3
Returns: 974688
4
4
4
Returns: 3640
1
4
2
Returns: 6
3
3
5
Returns: 0
3
4
4
Returns: 990
2
3
3
Returns: 20
4
3
5
Returns: 1584
10
7
35
Returns: 358906215
5
9
61
Returns: 0
4
4
6
Returns: 16016
3
1
1
Returns: 6
3
2
0
Returns: 2
3
4
6
Returns: 924
5
4
37
Returns: 0
8
9
95
Returns: 0
4
1
1
Returns: 8
82
6
79
Returns: 782694505
4
3
7
Returns: 0
50
1
25
Returns: 605552882
8
4
16
Returns: 601080390
8
10
32
Returns: 973945307
7
8
66
Returns: 0
4
4
8
Returns: 12870
19
12
67
Returns: 852330214
5
1
98
Returns: 0
54
46
38
Returns: 186037971
20
17
86
Returns: 218475535
4
3
0
Returns: 2
1
1
1
Returns: 0
9
13
39
Returns: 300396636
79
94
68
Returns: 866709725
84
59
2
Returns: 24556980
2
1
0
Returns: 2
4
4
1
Returns: 32
5
6
11
Returns: 109254600
12
10
76
Returns: 0
73
2
73
Returns: 910319061
13
6
74
Returns: 0
86
1
43
Returns: 203144612
3
2
4
Returns: 0
7
2
92
Returns: 0
31
92
7
Returns: 943888725
73
98
62
Returns: 270071910
1
80
40
Returns: 720596125
19
19
1
Returns: 722
4
3
2
Returns: 132
32
46
42
Returns: 989441983
19
13
33
Returns: 336401201
14
3
21
Returns: 257870674
5
26
65
Returns: 883560366
2
1
2
Returns: 0
2
2
1
Returns: 8
4
2
3
Returns: 112
15
1
1
Returns: 30
5
15
0
Returns: 2
3
4
3
Returns: 440
2
3
2
Returns: 30
1
9
0
Returns: 2
2
4
1
Returns: 16
12
14
23
Returns: 780981562
2
2
3
Returns: 0
4
2
5
Returns: 0
98
9
100
Returns: 447492791
24
2
24
Returns: 603457371
6
18
40
Returns: 964099272
3
3
0
Returns: 2
76
13
85
Returns: 421123626
13
4
8
Returns: 505076293
22
60
2
Returns: 1741080
16
14
46
Returns: 644256668
10
1
50
Returns: 0
1
2
1
Returns: 2
25
8
100
Returns: 407336795
9
20
100
Returns: 0
10
10
50
Returns: 538992043
4
1
2
Returns: 6
3
4
10
Returns: 0
10
20
100
Returns: 407336795
9
9
40
Returns: 676501747