program iepuri;
const modul=666013;
var t,k,i,j,x,y,z,a,b,c,n:longint;
m,m1,pow:array [1..3,1..3] of int64;
begin
assign(input,'iepuri.in');
reset(input);
assign(output,'iepuri.out');
rewrite(output);
readln(t);
for k:=1 to t do
begin
readln(x,y,z,a,b,c,n);n:=n-2;
for i:=1 to 3 do for j:=1 to 3 do begin m[i,j]:=0;pow[i,j]:=0; end;
m[3,1]:=x;m[3,2]:=y;m[3,3]:=z;
pow[1,3]:=c;pow[2,1]:=1;pow[2,3]:=b;pow[3,2]:=1;pow[3,3]:=a;
m1:=pow;
while n>0 do
begin
if n mod 2=1 then
begin
m1:=m;
m[1,1]:=(m1[1,1]*pow[1,1]+m1[1,2]*pow[2,1]+m1[1,3]*pow[3,1])mod modul;
m[1,2]:=(m1[1,1]*pow[1,2]+m1[1,2]*pow[2,2]+m1[1,3]*pow[3,2])mod modul;
m[1,3]:=(m1[1,1]*pow[1,3]+m1[1,2]*pow[2,3]+m1[1,3]*pow[3,3])mod modul;
m[2,1]:=(m1[2,1]*pow[1,1]+m1[2,2]*pow[2,1]+m1[2,3]*pow[3,1])mod modul;
m[2,2]:=(m1[2,1]*pow[1,2]+m1[2,2]*pow[2,2]+m1[2,3]*pow[3,2])mod modul;
m[2,3]:=(m1[2,1]*pow[1,3]+m1[2,2]*pow[2,3]+m1[2,3]*pow[3,3])mod modul;
m[3,1]:=(m1[3,1]*pow[1,1]+m1[3,2]*pow[2,1]+m1[3,3]*pow[3,1])mod modul;
m[3,2]:=(m1[3,1]*pow[1,2]+m1[3,2]*pow[2,2]+m1[3,3]*pow[3,2])mod modul;
m[3,3]:=(m1[3,1]*pow[1,3]+m1[3,2]*pow[2,3]+m1[3,3]*pow[3,3])mod modul;
end;
m1:=pow;
pow[1,1]:=(m1[1,1]*m1[1,1]+m1[1,2]*m1[2,1]+m1[1,3]*m1[3,1])mod modul;
pow[1,2]:=(m1[1,1]*m1[1,2]+m1[1,2]*m1[2,2]+m1[1,3]*m1[3,2])mod modul;
pow[1,3]:=(m1[1,1]*m1[1,3]+m1[1,2]*m1[2,3]+m1[1,3]*m1[3,3])mod modul;
pow[2,1]:=(m1[2,1]*m1[1,1]+m1[2,2]*m1[2,1]+m1[2,3]*m1[3,1])mod modul;
pow[2,2]:=(m1[2,1]*m1[1,2]+m1[2,2]*m1[2,2]+m1[2,3]*m1[3,2])mod modul;
pow[2,3]:=(m1[2,1]*m1[1,3]+m1[2,2]*m1[2,3]+m1[2,3]*m1[3,3])mod modul;
pow[3,1]:=(m1[3,1]*m1[1,1]+m1[3,2]*m1[2,1]+m1[3,3]*m1[3,1])mod modul;
pow[3,2]:=(m1[3,1]*m1[1,2]+m1[3,2]*m1[2,2]+m1[3,3]*m1[3,2])mod modul;
pow[3,3]:=(m1[3,1]*m1[1,3]+m1[3,2]*m1[2,3]+m1[3,3]*m1[3,3])mod modul;
n:=n div 2;
end;
writeln(m[3,3]);
end;
close(output);
end.