#include <stdio.h>

#define MOD 666013

int x, y, z, a, b, c, n, Fn;
int M[3][3];
int proto[3][3] = 	{ 
			{0, 0, 0}, 
			{1, 0, 0}, 
			{0, 1, 0}
			};
int O[3][3]; // matrice nula 
int I[3][3] = 		{ 
			{1, 0, 0},
			{0, 1, 0},
			{0, 0, 1}
			};

void afisaza(int T[3][3])
{
	int i, j;
	for(i = 0; i < 3; ++i) 
	{
		for(j = 0; j < 3; ++j) fprintf(stderr, "%d ", T[i][j]);
		fprintf(stderr, "\n");
	}
}

void copiazaMatrice(int dest[3][3], int src[3][3])
{
	int i, j;
	for(i = 0; i < 3; ++i)
		for(j = 0; j < 3; ++j)
			dest[i][j] = src[i][j];
}

void citesteTest() { scanf("%d%d%d%d%d%d%d", &x, &y, &z, &a, &b, &c, &n); }

void inmultesteMatrice(int dest[3][3], int src[3][3])
{
	int ad[3][3];
	copiazaMatrice(ad, dest); /* fac o copie pentru matricea dest */
	copiazaMatrice(dest, O); /* fac matricea dest egala cu matricea nula */

	int i, j, k;
	for(i = 0; i < 3; ++i)
	{
		for(j = 0; j < 3; ++j)
		{
			for(k = 0; k < 3; ++k) dest[i][j] += ((ad[i][k] * src[k][j]) % MOD);
			dest[i][j] = dest[i][j] % MOD;
		}
	}

}

#define MAXP 30

int puteri[MAXP][3][3];

void initPuteri()
{
	int i;
	for(i = 0; i < MAXP; ++i) copiazaMatrice(puteri[i], I);
	copiazaMatrice(puteri[1], M);
	for(i = 2; i < MAXP; ++i)
	{
			inmultesteMatrice(puteri[i], puteri[i - 1]);
			inmultesteMatrice(puteri[i], puteri[i - 1]);
	}
}

void ridicaMatrice(int q[3][3], int putere)
{
	int aux[3][3];
	copiazaMatrice(aux, I);
	int i = 0;
	while(putere)
	{
		if(putere % 2 == 1) inmultesteMatrice(aux, q);
		inmultesteMatrice(aux, puteri[i]); /* FIX */
		i++;
		putere /= 2;
	}
	copiazaMatrice(q, aux);
}

void rezolvaTest()
{
	/* creez matricea M */
	copiazaMatrice(M, proto);
	M[0][2] = c;
	M[1][2] = b;
	M[2][2] = a;


	/* initializez puteri */
	initPuteri();

	/* ridic matricea la puterea n - 3 */
	ridicaMatrice(M, n - 2);

	/* determin Fn */
	c = M[0][2];
	b = M[1][2];
	a = M[2][2];
	Fn = (x * c + y * b + z * a) % MOD;
}

void scrieRezultat()
{
	printf("%d\n", Fn);
}

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

	int teste;
	scanf("%d", &teste);
	
	while(teste--)
	{
		citesteTest();
		rezolvaTest();
		scrieRezultat();
	}

	return 0;
}