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