#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 i, j, k, c[3][3];
	for(i=0;i<=2;i++)
		for(j=0;j<=2;j++)
			c[i][j]=0;
	for(i=0;i<=2;i++)
		for(j=0;j<=2;j++)
			for(k=0;k<=2;k++)
			{
				c[i][j]+=a[i][k]*b[k][j];
				c[i][j]%=mod;
			}
	for(i=0;i<=2;i++)
		for(j=0;j<=2;j++)
			a[i][j]=c[i][j];
}
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[2][2], &v[1][2], &v[0][2], &n);
		v[0][0] = 0;
		v[0][1] = 0;
		v[1][0] = 1;
		v[1][1] = 0;
		v[2][0] = 0;
		v[2][1] = 1;
		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[2][2]*z)+(b[1][2]*y)+(b[0][2]*x))%mod);
	fprintf(g, "%s", "\n");
	}
	return 0;
}