// http://infoarena.ro/forum/?topic=218.0
//

#define _CRT_SECURE_NO_DEPRECATE
#include <cstdio>
#include <cassert>

#include <vector>
using namespace std;

const int MOD = 666013;

class matrix {
public:
	matrix (int nl, int nc) { // initializez matricea cu nl linii si nc coloane si cu 0 peste tot
		m = nl, n = nc;
		int i, j;

		for (i = 0; i < m; ++ i) {
			Mat.push_back(vector<int>());
			for (j = 0; j < n; ++ j)
				Mat[i].push_back(0);
		}
	}
	bool toMatrix(int nl, int nc, vector<int> Init) {
		if (nl != m && nc != n)
			return false;
		int i, j, k;
	
		for (i = 0, k = 0; i < m; ++ i)
			for (j = 0; j < n; ++ j, ++ k)
				Mat[i][j] = Init[k];
		return true;
	}

	void operator =(matrix Right) {
		int i, j;
		for (i = 0; i < m; ++ i)
			for (j = 0; j < n; ++ j)
				Mat[i][j] = Right.Mat[i][j];
	}
	matrix operator *(matrix Right) { // inmultirea propriu-zisa a 2 matrice
		int i, j, k;
		matrix result(m, Right.n);

		assert(n == Right.m);

		for (k = 0; k < n; ++ k)
			for (i = 0; i < m; ++ i)
				for (j = 0; j < Right.n; ++ j)
					result.Mat[i][j] = (result.Mat[i][j] + (Mat[i][k] * Right.Mat[k][j]) % MOD) % MOD;
		return result;
	}
	matrix exp(int pow) { // ridicarea la putere
		if (m != n) {
			matrix result(0, 0);
			return result;
		}

		if (pow == 1)
			return *this;
		if (pow % 2 == 1)
			return *this * exp(pow - 1);

		matrix result(n, n);
		result = exp(pow / 2);
		return result * result;	
	}

	int m, n;
	vector<vector<int> > Mat;
};

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

	int testCases, x, y, z, a, b, c, n;
	vector<int> Seed;
	matrix Seq(1, 3), Base(3, 3);

	for (scanf("%d ", &testCases); testCases > 0; -- testCases) {
		scanf("%d %d %d %d %d %d %d", &x, &y, &z, &a, &b, &c, &n);

		Seed.push_back(x), Seed.push_back(y), Seed.push_back(z);
		Seq.toMatrix(1, 3, Seed);
		Seed.clear();

		Seed.push_back(0), Seed.push_back(0), Seed.push_back(c), 
		Seed.push_back(1), Seed.push_back(0), Seed.push_back(b), 
		Seed.push_back(0), Seed.push_back(1), Seed.push_back(a);
		Base.toMatrix(3, 3, Seed);
		Seed.clear();

		Base = Base.exp(n - 2);

		Seq = Seq * Base;
		printf("%d\n", Seq.Mat[0][2]);
	}

	return 0;
}