Problem Statement
Time limit for this problem is 3 seconds.
This problem is about a plan-conquering board game. The board is a rectangle divided into R times C cells. The cells have coordinates (0, 0) to (R-1, C-1). Cells are adjacent if they share a side.
Each cell may contain a base. There can be at most one base per cell. Bases cannot be adjacent. Additionally, there cannot be any cell that would be adjacent to more than one base.
It is now our turn. Our strategy for the game dictates that we should place at least B bases in our first turn. In how many ways can we do that? Return that count modulo 10^9 + 7.
Definition
- Class:
- BasePlacement
- Method:
- count
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int count(int R, int C, int B)
- (be sure your method is public)
Constraints
- R and C will be positive.
- R * C will not exceed 190.
- B will be between 0 and R*C, inclusive.
Examples
2
3
1
Returns: 8
We can either place one base (2*3 = 6 options), or two bases. There are two ways to place two bases: they have to go into two opposite corners of the board.
8
10
2
Returns: 744999783
There are exactly 2,744,999,797 ways to place at least two bases onto this board. Remember that 744,999,783 is that count modulo 10^9 + 7.
10
10
47
Returns: 0
There is no way to fit 47 bases onto this board, and it's not even close.
1
1
1
Returns: 1
13
14
1
Returns: 218018740
2
95
48
Returns: 2
1
190
60
Returns: 427221125
190
1
65
Returns: 0
1
190
64
Returns: 1
2
95
2
Returns: 805026804
31
4
24
Returns: 58630344
18
10
10
Returns: 785334080
5
38
30
Returns: 182594370
10
19
1
Returns: 566411248
63
3
17
Returns: 177471408
13
9
9
Returns: 866215656
35
2
9
Returns: 327222570
10
19
28
Returns: 486728135
9
9
4
Returns: 499650533
12
15
2
Returns: 864444041
4
47
36
Returns: 330812894
2
95
5
Returns: 762165962
63
3
1
Returns: 874140738
10
4
4
Returns: 98157
14
8
12
Returns: 385521969
15
12
3
Returns: 864428878
13
14
1
Returns: 218018740
5
38
47
Returns: 0
13
1
2
Returns: 175
5
38
2
Returns: 328832162
21
9
37
Returns: 2493514
7
16
9
Returns: 951874974
12
9
8
Returns: 866544501
7
27
22
Returns: 790277436
190
1
7
Returns: 518065660
6
31
37
Returns: 26656242
8
23
21
Returns: 690859835
6
22
10
Returns: 281950515
17
11
1
Returns: 331542419
10
19
25
Returns: 981709542
18
6
19
Returns: 845319897
10
13
9
Returns: 573091930
12
15
16
Returns: 363813840
17
11
31
Returns: 101621008
6
17
13
Returns: 167765927
10
14
18
Returns: 31134897
14
6
6
Returns: 221496801
1
190
23
Returns: 376944756
10
8
7
Returns: 706298535
63
3
28
Returns: 966316570
17
11
15
Returns: 865260077
190
1
2
Returns: 564472595
21
9
33
Returns: 46668436
27
7
1
Returns: 701225175
13
14
34
Returns: 628513381
8
23
17
Returns: 122220896
3
7
2
Returns: 583
47
4
31
Returns: 619576015
13
13
16
Returns: 873805003
14
13
33
Returns: 329341830
17
11
26
Returns: 250670948
6
27
2
Returns: 73456882
31
6
35
Returns: 236306958
27
7
2
Returns: 701224986
8
23
1
Returns: 892843274
14
13
2
Returns: 218018558
54
2
20
Returns: 867349658
21
9
6
Returns: 848150698
8
1
1
Returns: 27
21
9
1
Returns: 939031179
4
47
1
Returns: 830745458
11
8
11
Returns: 278499046
124
1
10
Returns: 261661278
31
3
7
Returns: 208405458
31
6
2
Returns: 175287632
13
14
27
Returns: 878949660
10
13
17
Returns: 686298483
11
12
26
Returns: 100430
12
13
19
Returns: 697559159
95
2
1
Returns: 805026994
1
1
0
Returns: 2