#include <bits/stdc++.h>

using namespace std;
ifstream f("iepuri.in");
ofstream g("iepuri.out");
//------------------------------------
///Globale
const long long mod = 666013;
long long x,y,z,a,b,c,n,v[4][4],v2[4][4],v3[4][4],rest[4][4];
//------------------------------------
///Functii
void citire();
//------------------------------------
int main()
{
	citire();
	return 0;
}
//------------------------------------
void putere(long long put)
{
	for(int i = 1; i <= 3; ++i)
		for(int j = 1; j <= 3; ++j)
			rest[i][j] = 0;
	rest[1][1] = 1;
	rest[2][2] = 1;
	rest[3][3] = 1;
	while(put != 1)
	{
		if(put & 1)
		{
			v3[1][1] = v2[1][1] * rest[1][1] + v2[1][2] * rest[2][1] + v2[1][3] * rest[3][1];
			v3[1][2] = v2[1][1] * rest[1][2] + v2[1][2] * rest[2][2] + v2[1][3] * rest[3][2];
			v3[1][3] = v2[1][1] * rest[1][3] + v2[1][2] * rest[2][3] + v2[1][3] * rest[3][3];
			v3[2][1] = v2[2][1] * rest[1][1] + v2[2][2] * rest[2][1] + v2[2][3] * rest[3][1];
			v3[2][2] = v2[2][1] * rest[1][2] + v2[2][2] * rest[2][2] + v2[2][3] * rest[3][2];
			v3[2][3] = v2[2][1] * rest[1][3] + v2[2][2] * rest[2][3] + v2[2][3] * rest[3][3];
			v3[3][1] = v2[3][1] * rest[1][1] + v2[3][2] * rest[2][1] + v2[3][3] * rest[3][1];
			v3[3][2] = v2[3][1] * rest[1][2] + v2[3][2] * rest[2][2] + v2[3][3] * rest[3][2];
			v3[3][3] = v2[3][1] * rest[1][3] + v2[3][2] * rest[2][3] + v2[3][3] * rest[3][3];
			for(int i = 1; i <= 3; ++i)
				for(int j = 1; j <= 3; ++j)
					rest[i][j] = v3[i][j] % mod;
		}
		v3[1][1] = v2[1][1] * v2[1][1] + v2[1][2] * v2[2][1] + v2[1][3] * v2[3][1];
		v3[1][2] = v2[1][1] * v2[1][2] + v2[1][2] * v2[2][2] + v2[1][3] * v2[3][2];
		v3[1][3] = v2[1][1] * v2[1][3] + v2[1][2] * v2[2][3] + v2[1][3] * v2[3][3];
		v3[2][1] = v2[2][1] * v2[1][1] + v2[2][2] * v2[2][1] + v2[2][3] * v2[3][1];
		v3[2][2] = v2[2][1] * v2[1][2] + v2[2][2] * v2[2][2] + v2[2][3] * v2[3][2];
		v3[2][3] = v2[2][1] * v2[1][3] + v2[2][2] * v2[2][3] + v2[2][3] * v2[3][3];
		v3[3][1] = v2[3][1] * v2[1][1] + v2[3][2] * v2[2][1] + v2[3][3] * v2[3][1];
		v3[3][2] = v2[3][1] * v2[1][2] + v2[3][2] * v2[2][2] + v2[3][3] * v2[3][2];
		v3[3][3] = v2[3][1] * v2[1][3] + v2[3][2] * v2[2][3] + v2[3][3] * v2[3][3];
		for(int i = 1; i <= 3; ++i)
			for(int j = 1; j <= 3; ++j)
				v2[i][j] = v3[i][j] % mod;
        put /= 2;
	}
	v3[1][1] = v2[1][1] * rest[1][1] + v2[1][2] * rest[2][1] + v2[1][3] * rest[3][1];
	v3[1][2] = v2[1][1] * rest[1][2] + v2[1][2] * rest[2][2] + v2[1][3] * rest[3][2];
	v3[1][3] = v2[1][1] * rest[1][3] + v2[1][2] * rest[2][3] + v2[1][3] * rest[3][3];
	v3[2][1] = v2[2][1] * rest[1][1] + v2[2][2] * rest[2][1] + v2[2][3] * rest[3][1];
	v3[2][2] = v2[2][1] * rest[1][2] + v2[2][2] * rest[2][2] + v2[2][3] * rest[3][2];
	v3[2][3] = v2[2][1] * rest[1][3] + v2[2][2] * rest[2][3] + v2[2][3] * rest[3][3];
	v3[3][1] = v2[3][1] * rest[1][1] + v2[3][2] * rest[2][1] + v2[3][3] * rest[3][1];
	v3[3][2] = v2[3][1] * rest[1][2] + v2[3][2] * rest[2][2] + v2[3][3] * rest[3][2];
	v3[3][3] = v2[3][1] * rest[1][3] + v2[3][2] * rest[2][3] + v2[3][3] * rest[3][3];
	for(int i = 1; i <= 3; ++i)
		for(int j = 1; j <= 3; ++j)
			v2[i][j] = v3[i][j] % mod;
}
//------------------------------------
void rezolvare()
{
	v[3][1] = x;
	v[3][2] = y;
	v[3][3] = z;
	if(n <= 2)
	{
		g << v[3][n + 1] << '\n';
		return;
	}
	n -= 2;
	v2[1][1] = 0;
	v2[1][2] = 0;
	v2[1][3] = c;
	v2[2][1] = 1;
	v2[2][2] = 0;
	v2[2][3] = b;
	v2[3][1] = 0;
	v2[3][2] = 1;
	v2[3][3] = a;
	putere(n);
	g << (v[3][1] * v2[1][3] + v[3][2] * v2[2][3] + v[3][3] * v2[3][3]) % mod << '\n';
	return;
}
//------------------------------------
void citire()
{
	int t;
	f >> t;
	while(t--)
	{
		f >> x >> y >> z >> a >> b >> c >> n;
		rezolvare();
	}
}