#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%lld%lld", &x, &y, &z);
		fscanf(f,"%lld%lld%lld%lld", &v[0][0], &v[0][1], &v[0][2], &n);
		v[1][0] = 1;
		v[1][1] = 0;
		v[1][2] = 0;
		v[2][0] = 0;
		v[2][1] = 1;
		v[2][2] = 0;
		for(i=0;i<=2;i++)
			for(k=0;k<=2;k++)
				b[i][k]=v[i][k];
		//b[1][1]=b[2][2]=b[0][0]=1;
		for(n-=3;n;n>>=1)
		{
			if(1&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;
}