#include <cstdio>
#include <cstring>
using namespace std;
const unsigned int MOD = 666013;
typedef unsigned int ui;
ui A[4][4], a, b, c, x, y, z, n, t, R[4][4], T[4][4];

inline void times(ui A[4][4],ui B[4][4],ui C[4][4], ui n, ui m, ui q) {
	ui i, j, k;
//	memset(C, 0, sizeof(C));
	for(i = 1; i <= m; ++i)
		for(j = 1; j <= q; ++j)
			C[i][j] = 0;
	for(i = 1; i <= n; ++i)
		for(j = 1; j <= q; ++j)
			for(k = 1; k <= m; ++k)
				{C[i][j] += ((long long)A[i][k] * B[k][j]) % MOD;
					if(C[i][j] > MOD)
						C[i][j] -= MOD;
				}
}

inline void exp(ui w, ui C[4][4], ui n, ui m) {
	ui pow[4][4], B[4][4];
	ui i, j;

	for(i = 1; i <= n; ++i)
		for(j = 1; j <= m; ++j)
			pow[i][j] = A[i][j];

	for(ui step = 1; step <= w; step *= 2) {
		if(step & w){
		/*	for(i = 1; i <= n; ++i)
				for(j = 1; j <= m; ++j)
					B[i][j] = 0;
		*/	times(C, pow, B, n, m, m);
			for(i = 1; i <= n; ++i)
				for(j = 1; j <= m; ++j)
					C[i][j] = B[i][j];
		}

		
		times(pow, pow, B, n, m, m);
		
		for(i = 1; i <= n; ++i)
			for(j = 1; j <= m; ++j)
				pow[i][j] = B[i][j];
		
		}
}

int main() {
	freopen("iepuri.in", "r", stdin);
	freopen("iepuri.out", "w", stdout);
	scanf("%d", &t);
	ui i, j;
	
	for(;t; --t) {
		scanf("%d %d %d %d %d %d %d", &x, &y, &z, &a, &b, &c, &n);
		
		for(i = 1; i <= 3; ++i)
			for(j = 1; j <= 3; ++j)
				A[i][j] = R[i][j] = 0;
		R[1][1] = x;	R[1][2] = y;	R[1][3] = z;
		A[1][3] = c;	A[2][1] = 1;	A[2][3] = b;	A[3][2] = 1;	A[3][3] = a;
		
		exp(n - 2, R, 3, 3);
				
		printf("%d\n", R[1][3]);
	}

	return 0;
}