#include<cstdio>
#include<cstring>
#define ll long long
#define MOD 666013
void read(),solve();
ll i,t,N,X,Y,Z,M[5][5],SOL[5][5],j,k,aux,SOL1[5][5],afis;
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("iepuri.in","r",stdin);
	freopen("iepuri.out","w",stdout);
	scanf("%d",&t);
}
void solve()
{
	for(;t;--t)
	{
		memset(SOL1,0,sizeof(SOL1));
		memset(SOL,0,sizeof(SOL));
		memset(M,0,sizeof(M));
		scanf("%lld%lld%lld%lld%lld%lld%lld",&X,&Y,&Z,&M[1][1],&M[1][2],&M[1][3],&N);
		SOL[1][1]=SOL[2][2]=SOL[3][3]=1;
		M[2][1]=1;
		M[3][2]=1;
		N-=2;
		for(;N;N>>=1)
		{
			if(N&1)
			{
				for(i=1;i<=3;i++)
					for(j=1;j<=3;j++)
					{
						aux=0;
						for(k=1;k<=3;k++)
							aux+=SOL[i][k]*M[k][j];
						SOL1[i][j]=aux;
					}
				for(i=1;i<=3;i++)
					for(j=1;j<=3;j++)SOL[i][j]=SOL1[i][j]%MOD;
			}
			for(i=1;i<=3;i++)
				for(j=1;j<=3;j++)
				{
					aux=0;
					for(k=1;k<=3;k++)
						aux+=M[i][k]*M[k][j];
					SOL1[i][j]=aux;
				}
			for(i=1;i<=3;i++)
				for(j=1;j<=3;j++)M[i][j]=SOL1[i][j]%MOD;
		}
		afis=SOL[1][1]*Z+SOL[1][2]*Y+SOL[1][3]*X;
		printf("%lld\n",afis%MOD);
	}
	
}