#include<cstdio>
#define N 4
#define MOD 666013
long long a[N],copie[10000][N][N],m[N][N],rez[N][N];
int p;
void copiez(int x)
{
	for (int i=1; i<=3; ++i)
		for (int j=1; j<=3; ++j)
			copie[x][i][j]=m[i][j];
}
void m2()
{
	for (int i=1; i<=3; ++i)
		for (int j=1; j<=3; ++j)
	    {
	    	rez[i][j]=0;
		for (int k=1; k<=3; ++k)
			rez[i][j]=(rez[i][j]+((m[i][k]%MOD)*(m[k][j]%MOD))%MOD)%MOD;
	    }
	for (int i=1; i<=3; ++i)
		for (int j=1; j<=3; ++j)
		     m[i][j]=rez[i][j];   
}
void copieXm(int x)
{
    for (int i=1; i<=3; ++i)
	    for (int j=1; j<=3; ++j)
	    {
		    rez[i][j]=0;
		    for (int k=1; k<=3; ++k)
			    rez[i][j]=(rez[i][j]+((copie[x][i][k]%MOD)*(m[k][j]%MOD))%MOD)%MOD;
	    }
   for (int i=1; i<=3; ++i)
	   for (int j=1; j<=3; ++j)
		   m[i][j]=rez[i][j];
}
void putere(int p,int num)
{
	if (!p)
	{
		for (int i=1; i<=3;++i) 
			for(int j=1; j<=3; ++j)
				if (i==j)
					m[i][j]=1;
				else
					m[i][j]=0;
		return;
	}
	if (p&1)
	{
		copiez(num);
		m2();
		putere(p>>1,num+1);
        copieXm(num);
	}
	else
	{
		m2();
		putere(p>>1,num);
	}
}
void mXa()
{
	rez[1][1]=0;
	for (int k=1; k<=3; ++k)
		rez[1][1]=(rez[1][1]+((m[1][k]%MOD)*(a[k]%MOD))%MOD)%MOD;
}
void citire()
{
	freopen("iepuri.in","r",stdin);
	freopen("iepuri.out","w",stdout);
	short int t;
	scanf("%hd",&t);
	while (t--)
	{
		scanf("%lld%lld%lld%lld%lld%lld%d",&a[1],&a[2],&a[3],&m[3][3],&m[3][2],&m[3][1],&p);
		m[2][1]=0;m[2][2]=0;m[2][3]=1;
		m[1][1]=0;m[1][2]=1;m[1][3]=0;
		putere(p,0);
		mXa();
		printf("%lld\n",rez[1][1]%MOD);
	}
}
int main()
{
	citire();
	return 0;
}