#include<stdio.h>
#include<string.h>

#define MOD 666013

long long M[4][4], sol[4][4], rez;
int N, T;
int x, y, z;
int a, b, c;

void inmult_mat(long long A[4][4], long long B[4][4], long long C[4][4]) {
	
	int i, j, k;
	long long D[4][4], val;
	
	val = 0;
	for(i=1; i<=3; i++)
		for(j=1; j<=3; j++) {
			for(k=1; k<=3; k++)
				val += ((A[i][k] % MOD) * (B[k][j] % MOD)) % MOD;
			D[i][j] = val % MOD;
			val = 0;
		}
	memcpy(C,D,sizeof(D));
}

void put(int P) {
	
	for(; P; P>>=1) {
		if(P&1)
			inmult_mat(sol, M, sol);
		inmult_mat(M, M, M);
	}
}

void init_data() {
	
	scanf("%d %d %d",&x,&y,&z);
	M[3][1] = z;
	M[3][2] = y;
	M[3][3] = x;
	M[1][2] = M[2][3] = 1;
		
	sol[1][1] = sol[2][2] = sol[3][3] = 1;
	scanf("%d %d %d %d",&a,&b,&c,&N);
	N-=2;
}

void reset_data() {

	int i, j;
	for(i=1; i<=3; i++)
		for(j=1; j<=3; j++)
			M[i][j] = sol[i][j] = 0;
	rez = 0;
}

int main() {
	
	freopen("iepuri.in","r",stdin);
	freopen("iepuri.out","w",stdout);
	
	scanf("%d",&T);
	while(T--) {
		init_data();
		put(N);
		rez = ((sol[3][1] * a * 1LL)%MOD + (sol[3][2] * b * 1LL)%MOD + (sol[3][3] * c * 1LL)%MOD)%MOD;
		printf("%lld\n",rez);
		reset_data();
	}
	
	return 0;
}