TopCoder Statistics - Problem Statement

Problem Statement

This problem has a non-standard time limit: 5 seconds.

There is a rectangular board divided into H times W square cells. The board is currently empty. Cat Snuke is going to put tokens on some cells. He may only put at most one token onto each cell. When he's finished, each possible subrectangle of dimensions H2 times W2 must contain the same number of tokens.

You are given the ints H, W, H2, and W2. Count valid ways of placing the tokens. Return the answer modulo 1,000,000,007.

Definition

Class:: SubRectangles
Method:: countWays
Parameters:: int, int, int, int
Returns:: int
Method signature:: int countWays(int H, int W, int H2, int W2)
(be sure your method is public)

Constraints

H and W will be between 1 and 1,000,000,000, inclusive.
H2 and W2 will be between 1 and 4, inclusive.
H2 will be less than or equal to H.
W2 will be less than or equal to W.

Examples

2015

666

1

1

Returns: 2

Snuke can choose between two valid ways of placing the tokens: Either he puts one token onto each cell, or he leaves all cells empty.
3

3

3

2

Returns: 160

The following picture shows one possible way to put tokens ('o' is a cell with token, '-' is a cell without token): -oo o-- ooo There are two subrectangles with the dimensions 3 rows by 2 columns. Each of these contains four tokens.
6

3

4

1

Returns: 346
10

20

3

3

Returns: 705820974
123456789

987654321

3

4

Returns: 841175976
1000000000

1000000000

4

4

Returns: 294775952
1

1

1

1

Returns: 2
1000000000

1000000000

1

1

Returns: 2
537538007

988279542

1

1

Returns: 2
1000000000

1000000000

1

2

Returns: 140625003
215488404

312949792

1

2

Returns: 501963916
1000000000

1000000000

1

3

Returns: 471879292
76267071

186092455

1

3

Returns: 117221296
1000000000

1000000000

1

4

Returns: 117456091
314962285

108777344

1

4

Returns: 576447115
1000000000

1000000000

2

1

Returns: 140625003
903149395

19050635

2

1

Returns: 482291716
1000000000

1000000000

2

2

Returns: 281249995
934875039

211306883

2

2

Returns: 848140680
1000000000

1000000000

2

3

Returns: 435297829
642147272

268452149

2

3

Returns: 741259539
1000000000

1000000000

2

4

Returns: 134522251
576909845

798879133

2

4

Returns: 973358955
1000000000

1000000000

3

1

Returns: 471879292
549372606

200904750

3

1

Returns: 819756581
1000000000

1000000000

3

2

Returns: 435297829
641125761

615824533

3

2

Returns: 538916709
1000000000

1000000000

3

3

Returns: 457860648
87866888

928280505

3

3

Returns: 107488238
1000000000

1000000000

3

4

Returns: 795528520
547990792

126071906

3

4

Returns: 652588062
1000000000

1000000000

4

1

Returns: 117456091
679635007

828842146

4

1

Returns: 793105884
1000000000

1000000000

4

2

Returns: 134522251
965585461

518373373

4

2

Returns: 229602156
1000000000

1000000000

4

3

Returns: 795528520
982197866

440553560

4

3

Returns: 292626401
1000000000

1000000000

4

4

Returns: 294775952
658051644

71464784

4

4

Returns: 984057137
999999999

999999999

4

4

Returns: 34247703
999999999

999999998

4

4

Returns: 631146518
999999999

999999997

4

4

Returns: 275791433
999999999

999999996

4

4

Returns: 198330492
999999998

999999999

4

4

Returns: 631146518
999999998

999999998

4

4

Returns: 361883424
999999998

999999997

4

4

Returns: 452755501
999999998

999999996

4

4

Returns: 156883944
999999997

999999999

4

4

Returns: 275791433
999999997

999999998

4

4

Returns: 452755501
999999997

999999997

4

4

Returns: 684473377
999999997

999999996

4

4

Returns: 860483093
999999996

999999999

4

4

Returns: 198330492
999999996

999999998

4

4

Returns: 156883944
999999996

999999997

4

4

Returns: 860483093
999999996

999999996

4

4

Returns: 104707047

Statistics

Problem Statement for "SubRectangles"

Problem Statement

Definition

Constraints

Examples