#include <stdio.h>

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

void Inmulteste(long long **M1, long 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)) % 666013;
}

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

void ProcedeuRecursiv(int lev)
{
	if (lev == 1)
	{
	}
	else
	{
		ProcedeuRecursiv(lev / 2);
		
		Inmulteste(tmpRec, tmpRec);
		
		for (i = 0 ; i < 3; i++)
			for (j = 0 ; j < 3 ; j++)
				tmpRec[i][j] = rez[i][j];

		if (lev % 2 == 1)
			Inmulteste(tmpRec, mat);

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

void solve()
{
	long 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;
	
	for (i = 0 ; i < 3; i++)
			for (j = 0 ; j < 3 ; j++)
				tmpRec[i][j] = mat[i][j];

	ProcedeuRecursiv(aux - 2);
}

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("G%dG\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("%ld %ld %ld %ld %ld %ld %ld",&x,&y,&z,&a,&b,&c,&N);
		
		if (N == 3)
			printf("%ld\n", (a*x + b*y + c*z));
		else
		{
			solve();
			printf("%ld\n", ((rez[0][2]*x % 666013) + (rez[1][2]*y % 666013) + (rez[2][2]*z % 666013)) % 666013);
		}

		//algoritmClasic();
	}
}