#include <fstream>

using namespace std;

ifstream cin("iepuri.in");
ofstream cout("iepuri.out");

const int dim = 3, mod = 666013;

void matrix_multiplication(int (&A)[dim][dim], int (&B)[dim][dim]) {

	int AA[dim][dim], BB[dim][dim];
	for (int i = 0; i < dim; i++)
		for (int j = 0; j < dim; j++)
			AA[i][j] = A[i][j], BB[i][j] = B[i][j], A[i][j] = 0;

	for (int i = 0; i < dim; i++)
		for (int j = 0; j < dim; j++)
			for (int k = 0; k < dim; k++)
				A[i][j] = (A[i][j] + 1ll * AA[i][k] * BB[k][j]) % mod;
}

void fast_exponentiation(int (&A)[dim][dim], int exp) {

	int base[dim][dim];
	for (int i = 0; i < dim; i++)
		for (int j = 0; j < dim; j++)
			base[i][j] = A[i][j];

	exp--;

	for (int pow = 1; pow <= exp; pow <<= 1) {

		if ((exp & pow) != 0)
			matrix_multiplication(A, base);

		matrix_multiplication(base, base);
	}
}

void solve() {

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

	int A[dim][dim] = { {a, b, c}, {1, 0, 0}, {0, 1, 0} }, X[] = {z, y, x};

	fast_exponentiation(A, n - dim + 1);

	int ans = 0;
	for (int k = 0; k < dim; k++)
		ans = (ans + 1ll * A[0][k] * X[k]) % mod;

	cout << ans << "\n";
}

int main() {

	int t;
	cin >> t;

	while (t--)
		solve();
}