N friends have bought a chocolate that consists of R x C chocolate blocks and decide to split the chocolate into N pieces so that each friend gets at least B chocolate blocks.

They do the splitting in this way: the first friend breaks the chocolate into two pieces (by splitting it horizontally or vertically), takes one half and passes the other half to the second friend, the second friend breaks the chocolate into two pieces (by splitting horizontally or vertically), takes one half and passes the other half to the third friend… The last friend takes the remaining piece of chocolate. On how many ways the friends can split the chocolate into N pieces so that each of them gets at least B chocolate blocks?

Input

The first line of input contains one positive integer T (1 <= T <= 100), the number of test cases.

Each test case starts with a line that contains exactly four integers: R (1 <= R <= 50), C (1 <= C <= 50), B (1 <= B <= R*C) and N (2 <= N <= 10).

Output

For each test case, output the number of ways (modulo 1,000,000,007) the friends can split the chocolate into N pieces so that each of them gets at least B chocolate blocks.

Constraints

Time limit: 3 seconds
Memory limit: 64 megabytes

Examples

input
3
2 3 2 3
2 3 1 3
4 4 3 2

output
8
20
12

For the first example, the ways to split the chocolate are:

For the third example, the ways to split the chocolate are: