#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, int p)
{   if(p==0)
    {   for(int i=0;i<3;i++) for(int j=0;j<3;j++) B[i][j]=0;
        for(int i=0;i<3;i++) B[i][i]=1;
        return;
    }
    mat C,D;
    prod(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;}
        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;}
    }
    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;}
    }
}
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;
        prod(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;
}