#include <stdio.h>

long i, j, k;
long **rez;
long **mat;
long **tmpRec;
void init()
{
	rez = new long *[3];
	mat = new long *[3];
	tmpRec = new long *[3];
	for (int i = 0 ; i < 3; i++)
	{
		rez[i] = new long [3];
		mat[i] = new long [3];
		tmpRec[i] = new long [3];
	}
}

void Inmulteste(long **M1, long  **M2)
{
	for (i = 0 ; i < 3 ; i++)
		for (j = 0 ; j < 3 ; j++)
			rez[i][j] = 0;
	for (i = 0 ; i < 3; i++)
		for (j = 0 ; j < 3; j++)
			for (k = 0 ; k < 3; k++)
				rez[i][j] = (rez[i][j] + (M1[i][k]*M2[k][j])) % 666013;
}

int N, T, x, y, z, a, b, c;

void ProcedeuRecursiv(int lev, bool IsPar)
{
	if (lev == 1)
	{
	}
	else
	{
		ProcedeuRecursiv(lev / 2, lev % 2 == 0);

		for (i = 0 ; i < 3; i++)
			for (j = 0 ; j < 3 ; j++)
				tmpRec[i][j] = mat[i][j];
		
		Inmulteste(tmpRec, tmpRec);
		
		for (i = 0 ; i < 3; i++)
			for (j = 0 ; j < 3 ; j++)
				tmpRec[i][j] = rez[i][j];

		if (!IsPar)
			Inmulteste(tmpRec, mat);

		for (i = 0 ; i < 3; i++)
			for (j = 0 ; j < 3 ; j++)
				tmpRec[i][j] = rez[i][j];
	}
}

void solve()
{
	int aux = N;
	mat[0][0] = 0;mat[0][1] = 0;mat[0][2] = c;
	mat[1][0] = 1;mat[1][1] = 0;mat[1][2] = b;
	mat[2][0] = 0;mat[2][1] = 1;mat[2][2] = a;
	
	ProcedeuRecursiv(aux - 2, (aux - 2) % 2 == 0);
}

void algoritmClasic()
{
	long sum = 0;
	long l1 = x;
	long l2 = y;
	long l3 = z;
	for (long g = 3 ; g <= N; g++)
	{
		sum = (c*l1+b*l2+a*l3) % 666013;
		l1 = l2;
		l2 = l3;
		l3 = sum;
	}

	printf("%d\n", sum);
}

int main()
{
	freopen("iepuri.in", "r", stdin);
	freopen("iepuri.out", "w", stdout);
	init();

	scanf("%d", &T);
	for (int i = 0 ; i < T; i++)
	{
		scanf("%d %d %d %d %d %d %d",&x,&y,&z,&a,&b,&c,&N);
		
		/*if (N == 3)
			printf("%d\n", (a*x + b*y + c*z));
		else
		{
			solve();
			printf("%d\n", (rez[0][2]*x + rez[1][2]*y + rez[2][2]*z) % 666013);
		}*/

		algoritmClasic();
	}
}