#include<stdio.h> 
#define BAZA 666013

long long x, y, z, aj, bj, n, b[5][5], a[5][5], b1[5][5], i, j, nrt, k, c, ct[5][5], test, teste;
void mul(long long a[5][5], long long b[5][5]){
	
	for (int i = 1; i <= 3; i ++)
		for (int j = 1; j <= 3; j ++)
			for (int k = 1; k <= 3; k ++)
				b1[i][j] += (a[i][k]*b[k][j]) % BAZA;
	
	for (int i = 1; i <= 3; i ++)
		for (int j = 1; j <= 3; j ++)
			a[i][j] = b1[i][j], b1[i][j] = 0;
}
void prod(){
	while (n){
		if (n & 1 == 1)
			mul(b, ct);
		if (n != 1)
			mul(b, b);
		
		n >>= 1;
	}
}
void gol(){
	for (int i = 1; i <= 3; i ++)
		for (int j = 1; j <= 3; j ++)
			a[i][j] = 0, b[i][j] = 0, ct[i][j] = 0;
}
int main()
{
	freopen("iepuri.in", "rt", stdin);
	freopen("iepuri.out", "wt", stdout);
	
	scanf("%lld", &teste);
	
	for (test = 1; test <= teste; test ++){
		scanf("%lld%lld%lld%lld%lld%lld%lld", &a[1][1], &a[1][2], &a[1][3], &b[3][3], &b[2][3], &b[1][3], &n);
		
		b[2][1] = 1, b[3][2] = 1;
		
		for (i = 1; i <= 3; i ++)
			for (j = 1; j <= 3; j ++)
				ct[i][j] = b[i][j];
		
		n -= 3; 
		prod();
		mul(a, b);
		
		printf("%lld\n", a[1][3]);
		
		gol();
	}
	
	return 0;
}