#include <stdio.h>

#define P 666013

int H[3][3], M[3][3], temp[3][3];

void inmultire(int A[3][3], int B[3][3])
{
	int 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] = aux [i][j] + (A[i][k] * B[k][j]) % P;
				aux[i][j] %= P;
			}
		}

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


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

	if (n % 2) {	
		inmultire(H, H);
		pow_matrix(n / 2);
		inmultire(H, M);
	} else {
		inmultire(H, H);
		pow_matrix(n / 2);
	}
	
}

void afis(int M[3][3])
{
	int i,j ;
	for (i = 0; i < 3; i++) {
		for (j = 0; j < 3; j++) 
			printf("%d ", 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];	
		
			pow_matrix(N - 2);
//			afis(H);
			printf("%d\n",(int) ((H[0][0] * Z) % P + (H[0][1] * Y) % P + (H[0][2] * X) % P));

	}
}