no tags

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 testcase

### 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:
30 0 5 20 2 2 54 4 4 9

Output:
6210053388```

### 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. The Raven: 2012-04-14 02:08:34 WA with what I think is a correct algorithm. Is the judge output/judge input correct for Test Case(1) ? EDIT:Sorry for the trouble. Fixed test case, rejudged solutions. EDIT[TheRaven]: Thanks! Last edit: 2012-04-14 05:35:44 David Duncan: 2012-04-14 02:08:34 @Mitch Schwartz: Yeah, my mistake in only considering one line for some reason; the problem statement is good. Mitch Schwartz: 2012-04-14 02:08:34 @David Duncan: I think the problem statement is clear. A destination (x,y,z) is valid as long as 0<=x<=A etc. So there will be (A+1)*(B+1)*(C+1)-1 valid destinations to consider, and you need to find the sum of all possible adventures over all destinations. David Duncan: 2012-04-14 02:08:34 Neato problem, but...I don't understand the apparent discrepancy between the output/explanation and that "Rand travels in a straight line from the origin". In case #2, why are the points (0,0,2) and (0,2,0) relevant? Thanks.