Problem Statement
Any 2 dimensional space can be tiled (covered using tiles) using a fractal pattern called Rauzy Fractal. This is a very simple tiling pattern which follows a simple recurrence. We start with 3 tiles. In the first 3 steps, we lay down 1st tile, the 2nd tile, and the 3rd tile. Then in each consecutive step, we lay down whatever tiles were laid down in the previous three steps. Below is a simple illustration of the tiling process in each step where a, b and c denote the first 3 tiles.

a

b

c

abc

abc c b

abccb abc c

...

Now given the size of the first three tiles can you calculate the total area of the floor covered after N steps of tiling?

Input Format
First line gives the number of test cases T. Then each line after that has the size of the three tiles (a, b and c) followed by N (each separated by a space).

Constraints
1 ≤ T ≤ 5;
0 ≤ a, b, c ≤ 1000003;
0 ≤ N ≤ 10^9

Output Format
Print T lines, each line containing the total area covered, modulo the prime 1000003.

SAMPLE INPUT
5
1 1 1 1
1 1 1 2
1 1 1 4
1 2 3 4
1 2 3 6

SAMPLE OUTPUT
1
2
6
12
43

见题面

见题面