#	include <stdio.h>

const int prim = 666013;

int main(){
	
	long long M[3][3], R[3][3], AUX[3][3], n, x, y, z, a, b, c, k, r;
	
	FILE * fin = fopen("iepuri.in", "r");
	FILE * fout = fopen("iepuri.out", "w");
	
	fscanf(fin, "%lld", &k);
	
	while ( k ){
		
		//fin >> x >> y >> z >> a >> b >> c >> n;
		
		fscanf(fin, "%lld %lld %lld %lld %lld %lld %lld", &x, &y, &z, &a, &b, &c, &n);
		
		
		R[0][0] = 1; R[0][1] = 0; R[0][2] = 0;
		R[1][0] = 0; R[1][1] = 1; R[1][2] = 0;
		R[2][0] = 0; R[2][1] = 0; R[2][2] = 1;	
			
		int p = n, i;
				
		for (; p; p -= 1LL << (i - 1)) {
			
			M[0][0] = 0; M[0][1] = 1; M[0][2] = 0;
			M[1][0] = 0; M[1][1] = 0; M[1][2] = 1;
			M[2][0] = c; M[2][1] = b; M[2][2] = a;			
			
			for (i = 1; (1LL << i) <= p; i++) {
							
				AUX[0][0] = ( M[0][0] * M[0][0] + M[0][1] * M[1][0] + M[0][2] * M[2][0] ) % prim;
				AUX[0][1] = ( M[0][0] * M[0][1] + M[0][1] * M[1][1] + M[0][2] * M[2][1] ) % prim;
				AUX[0][2] = ( M[0][0] * M[0][2] + M[0][1] * M[1][2] + M[0][2] * M[2][2] ) % prim;
				
				AUX[1][0] = ( M[1][0] * M[0][0] + M[1][1] * M[1][0] + M[1][2] * M[2][0] ) % prim;
				AUX[1][1] = ( M[1][0] * M[0][1] + M[1][1] * M[1][1] + M[1][2] * M[2][1] ) % prim;
				AUX[1][2] = ( M[1][0] * M[0][2] + M[1][1] * M[1][2] + M[1][2] * M[2][2] ) % prim;
				
				AUX[2][0] = ( M[2][0] * M[0][0] + M[2][1] * M[1][0] + M[2][2] * M[2][0] ) % prim;
				AUX[2][1] = ( M[2][0] * M[0][1] + M[2][1] * M[1][1] + M[2][2] * M[2][1] ) % prim;
				AUX[2][2] = ( M[2][0] * M[0][2] + M[2][1] * M[1][2] + M[2][2] * M[2][2] ) % prim;
				
				M[0][0] = AUX[0][0]; M[0][1] = AUX[0][1]; M[0][2] = AUX[0][2];
				M[1][0] = AUX[1][0]; M[1][1] = AUX[1][1]; M[1][2] = AUX[1][2];
				M[2][0] = AUX[2][0]; M[2][1] = AUX[2][1]; M[2][2] = AUX[2][2];
			
			}
			
			AUX[0][0] = ( R[0][0] * M[0][0] + R[0][1] * M[1][0] + R[0][2] * M[2][0] ) % prim;
			AUX[0][1] = ( R[0][0] * M[0][1] + R[0][1] * M[1][1] + R[0][2] * M[2][1] ) % prim;
			AUX[0][2] = ( R[0][0] * M[0][2] + R[0][1] * M[1][2] + R[0][2] * M[2][2] ) % prim;
				
			AUX[1][0] = ( R[1][0] * M[0][0] + R[1][1] * M[1][0] + R[1][2] * M[2][0] ) % prim;
			AUX[1][1] = ( R[1][0] * M[0][1] + R[1][1] * M[1][1] + R[1][2] * M[2][1] ) % prim;
			AUX[1][2] = ( R[1][0] * M[0][2] + R[1][1] * M[1][2] + R[1][2] * M[2][2] ) % prim;
				
			AUX[2][0] = ( R[2][0] * M[0][0] + R[2][1] * M[1][0] + R[2][2] * M[2][0] ) % prim;
			AUX[2][1] = ( R[2][0] * M[0][1] + R[2][1] * M[1][1] + R[2][2] * M[2][1] ) % prim;
			AUX[2][2] = ( R[2][0] * M[0][2] + R[2][1] * M[1][2] + R[2][2] * M[2][2] ) % prim;
			
			
			R[0][0] = AUX[0][0]; R[0][1] = AUX[0][1]; R[0][2] = AUX[0][2];
			R[1][0] = AUX[1][0]; R[1][1] = AUX[1][1]; R[1][2] = AUX[1][2];
			R[2][0] = AUX[2][0]; R[2][1] = AUX[2][1]; R[2][2] = AUX[2][2];
			
				
		
		}
		
		r = ( R[0][0] * x + R[0][1] * y + R[0][2] * z ) % prim;
		
		fprintf(fout, "%lld\n", r);
		
		k--;
	}
	
	return 0;
	
	
}