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