#include <stdio.h>
#define mod 666013
using namespace std;
FILE *f=fopen("iepuri.in","r"), *g=fopen("iepuri.out","w");
void inmultire(long long int a[][3], long long int b[][3])
{
	long long int q,w,e,r,t,y,u,i,o;
	q=(a[0][0]*b[0][0]%mod+a[0][1]*b[1][0]+a[0][2]*b[2][0])%mod;
	w=(a[0][0]*b[0][1]+a[0][1]*b[1][1]+a[0][2]*b[2][1])%mod;
	e=(a[0][0]*b[0][2]+a[0][1]*b[1][2]+a[0][2]*b[2][2])%mod;
	r=(a[1][0]*b[0][0]+a[1][1]*b[1][0]+a[1][2]*b[2][0])%mod;
	t=(a[1][0]*b[0][1]+a[1][1]*b[1][1]+a[1][2]*b[2][1])%mod;
	y=(a[1][0]*b[0][2]+a[1][1]*b[1][2]+a[1][2]*b[2][2])%mod;
	u=(a[2][0]*b[0][0]+a[2][1]*b[1][0]+a[2][2]*b[2][0])%mod;
	i=(a[2][0]*b[0][1]+a[2][1]*b[1][1]+a[2][2]*b[2][1])%mod;
	o=(a[2][0]*b[0][2]+a[2][1]*b[1][2]+a[2][2]*b[2][2])%mod;
	a[0][0]=q;
	a[0][1]=w;
	a[0][2]=e;
	a[1][0]=r;
	a[1][1]=t;
	a[1][2]=y;
	a[2][0]=u;
	a[2][1]=i;
	a[2][2]=o;
}
int main()
{
	long long int j, i, v[3][3], b[3][3], x, y, z, n, t, k;
	fscanf(f,"%lld", &t);
	for(j=1;j<=t;j++)
	{
		fscanf(f,"%lld%d%lld", &x, &y, &z);
		fscanf(f,"%lld%lld%lld%lld", &v[0][0], &v[0][1], &v[0][2], &n);
		v[1][0]=v[2][1]=1;
		v[1][1]=v[2][0]=v[1][2]=v[2][2]=0;
		for(i=0;i<=2;i++)
			for(k=0;k<=2;k++)
				b[i][k]=0;
		b[1][1]=b[2][2]=b[0][0]=1;
		n-=2;
		for(i=0;(1<<i)<=n;i++)
		{
			if((1<<i)&n)
				inmultire(b, v);
			inmultire(v, v);
		}
	fprintf(g, "%lld", ((b[0][0]*z)%mod+(b[0][1]*y)%mod+(b[0][2]*x)%mod)%mod);
	fprintf(g, "%s", "\n");
	}
	return 0;
}