Rand has been sitting in a spaceship at the point (0, 0, 0) for a long time. One day, he got bored and decided to undertake an adventure.

Deciding upon an adventure has several complicated steps. First, Rand chooses a destination point (x, y, z) different from (0, 0, 0) such that 0 <= x <= A, 0 <= y <= B, 0 <= z <= C. To go to this point, Rand travels in a straight line from the origin. As a result, he might encounter several other lattice points in the way. Each part of the journey between two consecutive lattice points encountered is called a phase.( For example if (x, y, z) = (1, 2, 3) then there is only one phase (0, 0, 0) → (1, 2, 3), while if (x, y, z) = (3, 0, 3) then there are 3 phases (0, 0, 0) → (1, 0, 1) → (2, 0, 2) → (3, 0, 3) ).

In each phase Rand chooses one of K different activities that he can undertake to pass the time. You need to calculate the total number of different adventures possible, modulo 1000000007 (1e9+7). Two adventures are considered different if they have different destination points, or if the activity undertaken during any of the corresponding phases is different.

Input

The first line contains the number T, the number of test cases.
T lines follow, each contains the integers A, B, C, K, corresponding to one test case

Output

Output T lines, each with one integer as the answer for the corresponding test case.

Constraints

T <= 1000
0 <= A, B, C <= 50000
1 <= K <= 10

Example

Input:
3
0 0 5 2
0 2 2 5
4 4 4 9

Output:
62
100
53388

Explanation

In the first test case, if Rand chooses (0, 0, 1) as destination point, then there are 2 possible adventures. Similarly for (0, 0, 2), (0, 0, 3), (0, 0, 4) and (0, 0, 5), the number of adventures corresponding to each are 4, 8, 16, 32 respectively. The total number of adventures is 2+4+8+16+32=62.

In the second test case, for points (0, 0, 2), (0, 2, 0) and (0, 2, 2) there are 25 adventures each, while for the rest of the 5 valid points, there are 5 adventures each. So total is 100.