#include <fstream>

using namespace std;

ifstream fin("iepuri.in");
ofstream fout("iepuri.out");

const int mod = 666013;

long long x[4], y[4][4], z[4][4];

void inmultire(long long m1[4][4], long long m2[4][4])
{
	long long aux[4][4] = { 0 };
	for (int i = 1; i <= 3; i++)
		for (int j = 1; j <= 3; j++)
			for (int k = 1; k <= 3; k++)
				aux[i][j] += (m1[i][k] * m2[k][j]) % mod;
	for (int i = 1; i <= 3; i++)
		for (int j = 1; j <= 3; j++)
			z[i][j] = aux[i][j] % mod;
}

void putere(long long p)
{
	if (p == 1)
	{
		for (int i = 1; i <= 3; i++)
			for (int j = 1; j <= 3; j++)
				z[i][j] = y[i][j];
	}
	else
	{
		if (p % 2 == 0)
		{
			putere(p / 2);
			inmultire(z, z);
		}
		else
		{
			putere(p - 1);
			inmultire(y, z);

		}
	}
}

int main()
{
	int t;
	fin >> t;
	y[2][1] = 1;
	y[3][2] = 1;
	for (int i = 1; i <= t; i++)
	{
		long long a, b, c, n;
		fin >> x[1] >> x[2] >> x[3] >> a >> b >> c >> n;
		y[1][3] = c;
		y[2][3] = b;
		y[3][3] = a;
		putere(n - 2);
		fout << (x[1] * z[1][3] + x[2] * z[2][3] + x[3] * z[3][3]) % mod << '\n';
	}
	return 0;
}