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


Added by:Rudradev Basak
Date:2012-03-30
Time limit:3.134s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem, used for ACM Indo-Pak Contest

hide comments
2012-04-14 02:08:34 The Raven
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
2012-04-14 02:08:34 David Duncan
@Mitch Schwartz: Yeah, my mistake in only considering one line for some reason; the problem statement is good.
2012-04-14 02:08:34 Mitch Schwartz
@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.
2012-04-14 02:08:34 David Duncan
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.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.