#include <stdio.h>

#define P 666013

long long H[3][3], M[3][3], AUX[3][3];

void inmultire(long long A[3][3], long long B[3][3])
{
	long long aux[3][3];
	int i, j, k;
	for (i = 0; i < 3; i++)
        for (j = 0; j < 3; j++) {
			aux[i][j] = 0;
			for (k = 0; k < 3; k++) {
				aux[i][j] += ((long long)A[i][k] * B[k][j]) % P;
				aux[i][j] %= P;
			}
		}

	for (i = 0; i < 3; i++)
		for (j = 0; j < 3; j++)
			A[i][j] = aux[i][j];
}


void pow_matrix(int n)
{
	if (n == 1) {
		return;
	}

	if (n % 2) {
		inmultire(AUX, H);
		pow_matrix(n - 1);
	} else {
		inmultire(H, H);
		pow_matrix(n / 2);
	}
	
}

void afis(long long M[3][3])
{
	int i,j ;
	for (i = 0; i < 3; i++) {
		for (j = 0; j < 3; j++) 
			printf("%d ",(int) M[i][j]);
		printf("\n");
	}
}

int main(void)
{
	FILE *f_in = freopen("iepuri.in", "rt", stdin);
	FILE *f_out = freopen("iepuri.out", "wt", stdout);

	long long T, X, Y, Z, A, B, C, N;
	scanf("%lld", &T);
	int i, j;
	

	M[1][0] = 1;
	M[2][1] = 1;

	while (T--) {
	
		scanf("%lld %lld %lld %lld %lld %lld %lld", &X, &Y, &Z, &A, &B, &C, &N);
		M[0][0] = A;
		M[0][1] = B;
		M[0][2] = C;

		for (i = 0; i < 3; i++)
			for (j = 0; j < 3; j++) {
				H[i][j] = M[i][j];	
				AUX[i][j] = 0;
			}	
			
		AUX[0][0] = 1;
		AUX[1][1] = 1;
		AUX[2][2] = 1;

		pow_matrix(N - 2);
		inmultire(H, AUX);
		printf("%d\n",(int) ((long long) H[0][0] * Z + H[0][1] * Y + H[0][2] * X) % P);

	}
}