Program Iepuri;  
      
    const fin = 'iepuri.in';  
         fout = 'iepuri.out';  
      
    type tmatrix3x3 = array[1..3,1..3] of int64;  
      
    var t,x,y,z,a,b,c,n: longint;  
                      r: array[1..100] of longint;  
                tx, x3: tmatrix3x3;  
     
   function mmx(m1, m2: tmatrix3x3): tmatrix3x3;  
   var i,j: byte;  
   begin  
    for i:=1 to 3 do  
    for j:=1 to 3 do  
            mmx[i,j]:=((m1[i,1]*m2[1,j] mod 666013) + (m1[i,2]*m2[2,j] mod 666013)  
                     +(m1[i,3]*m2[3,j] mod 666013)) mod 666013;  
   end;  
     
   function get(kk: longint): tmatrix3x3;  
   var kkx: tmatrix3x3;  
   begin  
    if kk = 1 then begin
                   get:=tx;
                   exit;
                   end;  
     
    if kk mod 2 = 0 then  
       begin  
         kkx:=get(kk div 2);  
         get:=mmx(kkx, kkx);  
         exit;  
       end  
       else  
       begin  
         kkx:=get(kk div 2);  
         get:=mmx( mmx( kkx, kkx), tx);  
         exit;  
       end;  
   end;  
     
   procedure solve(k: longint);  
   var fmx: tmatrix3x3;  
   begin  
    tx[1,1]:=A; tx[1,2]:=B; tx[1,3]:=C;  
    tx[2,1]:=1; tx[2,2]:=0; tx[2,3]:=0;  
    tx[3,1]:=0; tx[3,2]:=1; tx[3,3]:=0;  
     
    x3[1,1]:=z; x3[1,2]:=0; x3[1,3]:=0;  
    x3[2,1]:=y; x3[2,2]:=0; x3[2,3]:=0;  
    x3[3,1]:=x; x3[3,2]:=0; x3[3,3]:=0;  
     
    dec(n,2);  
    fmx:=get(n);  
    fmx:=mmx(fmx, x3);  
    r[k]:=fmx[1,1] mod 666013;  
   end;  
     
   procedure load;  
   var f: text; i: byte;  
   begin  
    assign(f, fin); reset(f);  
    readln(f, t);  
    for i:=1 to t do  
         begin  
           readln(f, x, y, z, a, b, c, n);  
         solve(i);  
         end;  
    close(f);  
   end;  
     
   procedure save;  
   var f: text; i: byte;  
   begin  
    assign(f, fout); rewrite(f);  
    for i:=1 to t-1 do writeln(f, r[i]);  
    write(f, r[t]);  
    close(f);  
   end;  
     
   begin  
   load;  
   save;  
   end.