#include <cstdio>
#include <cstring>

const int MOD = 666013;

int Z[4][4], F[4][4], t, x, y, z, a, b, c, n, exp;

void mult (int A[4][4], int B[4][4], int n, int m) {
	
	int C[4][4], i, j, k;
	
	memset (C, 0, sizeof (C));
	
	for (i = 1; i <= n; i++)
		for (j = 1; j <= m; j++)
			for (k = 1; k <= n; k++) {
				C[i][j] += (1LL * A[i][k] * B[k][j]) % MOD;
				if (C[i][j] >= MOD)
					C[i][j] -= MOD;
			}
	
	memcpy (B, C, sizeof (C));
}

int main () {
	
	freopen ("iepuri.in", "r", stdin);
	freopen ("iepuri.out", "w", stdout);
	
	scanf ("%d", &t);
	
	while (t--) {
		scanf ("%d %d %d %d %d %d %d", &x, &y, &z, &c, &b, &a, &n);
		
		F[1][1] = x, F[2][1] = y, F[3][1] = z;
		
		exp = n - 2;
		
		Z[1][1] = 0, Z[1][2] = 1, Z[1][3] = 0;
		Z[2][1] = 0, Z[2][2] = 0, Z[2][3] = 1;
		Z[3][1] = a, Z[3][2] = b, Z[3][3] = c;
		
		while (exp > 0) {
			if (exp & 1)
				mult (Z, F, 3, 1);
			
			mult (Z, Z, 3, 3);
			exp >>= 1;
		}
		
		printf ("%d\n", F[3][1]);
	}
	
	return 0;
}