#include <iostream>
#include <fstream>
#define mod 666013
using namespace std;
ifstream f("iepuri.in");
ofstream g("iepuri.out");
 int n,fib[5][5],m[5][5],m2[5][5];
 void Mult(int a[][5],int b[][5])
 { int i,j,t,res[5][5],l1=a[0][0],c1=a[0][1],l2=b[0][0],c2=b[0][1];

     for(i=1;i<=l1;i++)
      for(j=1;j<=c2;j++)
      { res[i][j]=0;
         for(t=1;t<=c1;t++)
          res[i][j]+=1LL*(a[i][t]%mod)*(b[t][j]%mod)%mod;

       res[i][j]%=mod;
      }

   for(i=1;i<=l1;i++)
    for(j=1;j<=c2;j++)
     a[i][j]=res[i][j];
 }

 int Solve(int x,int y,int z,int a,int b,int c,int n)
 { int i,j;
     if (!n) return x; if (n==1) return y; if (n==2) return z;
    for(i=1;i<=3;i++)
     for(j=1;j<=3;j++)
     {m[i][j]=0; m2[i][j]=0; fib[i][j]=0;}

     fib[0][0]=1; fib[0][1]=3;

     fib[1][1]=x; fib[1][2]=y; fib[1][3]=z;

     m[0][0]=m[0][1]=m2[0][0]=m2[0][1]=3;

     m[1][1]=m[2][2]=m[3][3]=1;

     m2[1][3]=c; m2[2][1]=1; m2[2][3]=b;
     m2[3][2]=1; m2[3][3]=a;

      n-=2;
    for(i=0;i<=31;i++)
    { if (n&(1LL<<i)) Mult(m,m2);
      Mult(m2,m2);
    }

   Mult(fib,m);

   return fib[1][3];
 }

int main()
{ int i,t,x,y,z,a,b,c,n;
  f>>t;
  for(i=1;i<=t;i++)
  { f>>x>>y>>z>>a>>b>>c>>n;

      g<<Solve(x,y,z,a,b,c,n)<<"\n";
  }
    return 0;
}