#include<fstream>
#define M 666013
using namespace std;
ifstream f("iepuri.in"); ofstream g("iepuri.out");
int T,n,a,b,c,x,y,z,nr,p;
typedef long long mat[3][3];
mat A,U;
void prod(mat A, mat B, int p)
{mat C,D; int i,j,k;
 if(p==0)
     {for(i=0; i<3; i++) for(j=0; j<3; j++) B[i][j]=0;
      for(i=0; i<3; i++) B[i][i]=1;
     }
    else
     {prod(A,C,p/2);
      if(p%2)
        {for(i=0; i<3; i++) for(j=0; j<3; j++)
          {D[i][j]=0; for(k=0; k<3; k++) D[i][j]+=C[i][k]*C[k][j]; D[i][j]%=M;}
         for(i=0; i<3; i++) for(j=0; j<3; j++)
          {B[i][j]=0; for(k=0; k<3; k++) B[i][j]+=D[i][k]*A[k][j]; B[i][j]%=M;}
        }
        else
        {for(i=0; i<3; i++) for(j=0; j<3; j++)
          {B[i][j]=0; for(k=0; k<3; k++) B[i][j]+=C[i][k]*C[k][j]; B[i][j]%=M;}
        }
     }
}
int main()
{f>>T;
 A[0][0]=A[0][1]=A[1][1]=A[2][0]=0; A[1][0]=A[2][1]=1;
 while(T)
     {f>>x>>y>>z>>a>>b>>c>>n;
      p=n-2;
      A[0][2]=c; A[1][2]=b; A[2][2]=a;
      prod(A,U,p);
      nr=(x*U[0][2]+y*U[1][2]+z*U[2][2])%M;
      g<<nr<<'\n';
      T--;
     }
 g.close(); return 0;
}