program gaju;
const q=666013;
type matrix=array[1..3,1..3]of int64;
var f,g:text;
    v,v1:matrix;
    i,t,a,b,c,x,y,z,n:longint;

procedure inm(var a:matrix;b:matrix);
var i,j,k:byte;
    x:int64;
    c:matrix;
begin
for i:=1 to 3 do
    for j:=1 to 3 do begin
        c[i,j]:=0;
        for k:=1 to 3 do begin
        x:=(a[i,k]*b[k,j])mod q;
        c[i,j]:=(c[i,j]+x)mod q;
    end;end;
a:=c;
end;

procedure exp(n:longint);
begin
if n=1 then v:=v1
       else if n mod 2=0 then begin
                                exp(n div 2);
                                inm(v,v);
                               end
                          else begin
                                exp(n-1);
                                inm(v,v1);
                               end;
end;


begin
assign(f,'iepuri.in');reset(f);
assign(g,'iepuri.out');rewrite(g);
readln(f,t);
for i:=1 to t do begin
    readln(f,x,y,z,a,b,c,n);
    v[1,1]:=0;v[1,2]:=1;v[1,3]:=0;
    v[2,1]:=0;v[2,2]:=0;v[2,3]:=1;
    v[3,1]:=c;v[3,2]:=b;v[3,3]:=a;
    v1:=v;
    exp(n);
    v1[1,1]:=x;v1[1,2]:=0;v1[1,3]:=0;
    v1[2,1]:=y;v1[2,2]:=0;V1[2,3]:=0;
    V1[3,1]:=z;v1[3,2]:=0;v1[3,3]:=0;
    inm(v,v1);
    writeln(g,v[1,1]);
end;
close(f);close(g);
end.