JOIN

 Problem Statement

Problem Statement for SubRectangles

### 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

0)

 `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.
1)

 `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.
2)

 `6` `3` `4` `1`
`Returns: 346`
3)

 `10` `20` `3` `3`
`Returns: 705820974`
4)

 `123456789` `987654321` `3` `4`
`Returns: 841175976`
5)

 `1000000000` `1000000000` `4` `4`
`Returns: 294775952`

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
2015 TopCoder Open Algorithm Round 3A - Division I, Level Three