ADVNTURE  Adventure
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: 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.
hide comments
The Raven:
20120414 02:08:34
WA with what I think is a correct algorithm. Is the judge output/judge input correct for Test Case(1) ?


David Duncan:
20120414 02:08:34
@Mitch Schwartz: Yeah, my mistake in only considering one line for some reason; the problem statement is good. 

Mitch Schwartz:
20120414 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:
20120414 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. 
Added by:  Rudradev Basak 
Date:  20120330 
Time limit:  3.134s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own Problem, used for ACM IndoPak Contest 