#include <iostream>
#include <cstdio>

using namespace std;

const long long PRIM = 666013;

class Mat9
{
	long long mat[3][3];

public:
	Mat9(long long a, long long b, long long c)
	{
		mat[0][0] = mat[0][2] = mat[1][0] = mat[1][1] = 0;
		mat[0][1] = mat[1][2] = 1;
		mat[2][0] = a;
		mat[2][1] = b;
		mat[2][2] = c;
	}

	Mat9()
	{
		for (int i = 0; i < 3; ++i)
			for (int j = 0; j < 3; ++j)
				mat[i][j] = 0;
	}

	void makeIdentity()
	{
		for (int i = 0; i < 3; ++i)
			mat[i][i] = 1;
	}

	Mat9 operator*(Mat9& b)
	{
		Mat9 res;
		for (int i = 0; i < 3; ++i)
			for (int j = 0; j < 3; ++j)
				for (int k = 0; k < 3; ++k)
				{
					res.mat[i][j] += mat[i][k] * b.mat[k][j];
					res.mat[i][j] %= PRIM;
				}

		return res;
	}

	long long mul(long long a, long long b, long long c)
	{
		return (a * mat[2][0] + b * mat[2][1] + c * mat[2][2]) % PRIM;
	}
};

Mat9 results[100];

void solveInstance(long long x, long long y, long long z, long long a, long long b, long long c, int n)
{
	results[0] = Mat9(z, y, x);

	n -= 2;

	int r = 1;

	while ((1 << r) <= n)
	{
		results[r] = results[r - 1] * results[r - 1];
		++r;
	}

	Mat9 result;
	result.makeIdentity();
	
	r = 0;
	while ((1 << r) <= n)
	{
		if ((1 << r) & n)
		{
			result = result * results[r];
		}
		++r;
	}

	cout << result.mul(a, b, c) << '\n';

}

void solve()
{
	long long x, y, z, a, b, c;
	int n;

	cin >> x >> y >> z >> a >> b >> c >> n;

	solveInstance(x, y, z, a, b, c, n);
}

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

	int t;
	cin >> t;
	
	for (int i = 0; i < t; ++i)
		solve();

	return 0;
}