#include<cstdio>
const int Q=666013;
int n,a,b,c,x,y,z,pppp,pp[4][4],A[4][4];
void prod(int X[4][4],int Y[4][4])
{
	int Z[4][4];
	for(int i=1;i<=3;i++)
		for(int j=1;j<=3;j++)
		{
			Z[i][j]=0;
			for(int k=1;k<=3;k++)
				Z[i][j]=(Z[i][j]+((long long)X[i][k]*Y[k][j])%Q)%Q;
		}
	for(int i=1;i<=3;i++)
		for(int j=1;j<=3;j++)
			X[i][j]=Z[i][j];
}
void put(int p)
{
    pp[1][1]=1;pp[1][2]=0;pp[1][3]=0;
	pp[2][1]=0;pp[2][2]=1;pp[2][3]=0;
	pp[3][1]=0;pp[3][2]=0;pp[3][3]=1;
    A[1][1]=a;A[1][2]=b;A[1][3]=c;
	A[2][1]=1;A[2][2]=0;A[2][3]=0;
	A[3][1]=0;A[3][2]=1;A[3][3]=0;
    while(p)
    {
        if(p%2==1)
            prod(pp,A);
        prod(A,A);
        p/=2;
    }
    int V[4][4];
    V[1][1]=z;V[1][2]=0;V[1][3]=0;
    V[2][1]=y;V[2][2]=0;V[2][3]=0;
    V[3][1]=x;V[3][2]=0;V[3][3]=0;
    prod(pp,V);
	printf("%d\n",pp[1][1]);
}

int main()
{
	freopen("iepuri.in","r",stdin);
	freopen("iepuri.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d%d%d%d%d",&a,&b,&c,&x,&y,&z,&pppp);
        put(pppp-2);
    }
	return 0;
}