#include <bits/stdc++.h>
using namespace std;
ifstream fin ("iepuri.in"); ofstream fout ("iepuri.out");
const int mod  = 666013;
long long n, a[5], x, y, z, d, e, ff, nrd, mat[5][5];

void mult (long long a[5][5], long long b[5][5])
{
	long long ans[5][5];
	for (long long i = 1; i <= 3; i++)
		for (long long j = 1; j <= 3; j++)
			ans[i][j] = 0;
	for (long long i = 1; i <= 3; i++)
		for (long long j = 1; j <= 3; j++)
			for (long long k = 1; k <= 3; k++)
				ans[i][j] = (ans[i][j] + a[i][k] * b[k][j]) % mod;
	for (long long i = 1; i <= 3; i++)
		for (long long j = 1; j <= 3; j++)
			a[i][j] = ans [i][j];
}

void lgput (long long a[5][5], long long p)
{
	long long copie[5][5];
	for (long long i = 1; i <= 3; i++)
		for (long long j = 1; j <= 3; j++)
		{
			copie [i][j] = a[i][j];
			if (i == j) a[i][j] = 1;
			else a[i][j] = 0;
		}
	while (p)
	{
		if (p & 1) mult (a, copie);
		mult (copie, copie);
		p >>= 1;
	}
}

int main ()
{
	fin >> n;
	for (; n; n--)
	{
		fin >> x >> y >> z >> d >> e >> ff >> nrd;
		memset (a, 0, sizeof(a));
		memset (mat, 0, sizeof(mat));
		a[1] = z, a[2] = y, a[3] = x;
		mat[1][1] = d, mat[1][2] = e, mat[1][3] = ff;
		mat[2][1] = mat[3][2] = 1;
		if (nrd <= 2) fout << a[nrd + 1] << '\n';
		else
		{
			lgput(mat, nrd - 2);
			long long ans[4];
			for (int j = 1; j <= 3; j++)
				ans[j] = 0;
			for (int i = 1; i <= 3; i ++)
				for (int k = 1; k <= 3; k++)
					ans[i] = (ans[i] + mat [i][k] * a[k]) % mod;
				fout << ans[1] << '\n';
		}
	}
	return 0;
}