#include<cstdio>
#include<string.h>
#define cst 666013
void inmultire(long long a[3][3],long long b[3][3])
{
int i,j,k;
long long c[3][3];
memset(c,0,sizeof(c));
for(i=0;i<3;i++)
	for(j=0;j<3;j++)
		for(k=0;k<3;k++)
			c[i][j]+=(a[i][k]*b[k][j])%cst;
	
		for(i=0;i<3;i++)
			for(j=0;j<3;j++)
				b[i][j]=(c[i][j])%cst;
}

int main()
{
long long m1[3][3],m2[3][3];
long long i,j,n,t,x,y,z,a,b,c,p;
freopen("iepuri.in","r",stdin);
freopen("iepuri.out","w",stdout);
scanf("%d",&t);
for(i=1;i<=t;i++)
{
	memset(m1,0,sizeof(m1));
	memset(m2,0,sizeof(m2));
	scanf("%lld %lld %lld %lld %lld %lld %lld",&m2[2][0],&m2[1][0],&m2[0][0],&m1[0][0],&m1[0][1],&m1[0][2],&n);
	n-=2;
	m1[1][0]=1;m1[2][1]=1;
	p=n;
	for(p=n;p;p>>=1)
	{
		if(p&1)
		{
			inmultire(m1,m2);
		}
		inmultire(m1,m1);
	}
	printf("%lld\n",m2[0][0]);
}

return 0;
}