#include<stdio.h>

using namespace std;

#define MOD 666013

long long int A[4][4], B[4][4], C[4][4];
long long int n;
int a, b, c, x, y, z, t, i, j, k;

int main()
{
	FILE *f = fopen("iepuri.in", "r");
	
	fscanf(f, "%d", &t);
	
	FILE *g = fopen("iepuri.out", "w");
	
	while(t)
	{
		fscanf(f, "%d %d %d %d %d %d %lld", &x, &y, &z, &a, &b, &c, &n);
		
		for(i = 1; i <= 3; ++i)
			for(j = 1; j <= 3; ++j)
				A[i][j] = B[i][j] = C[i][j] = 0;
			
		A[1][1] = z, A[2][1] = y, A[3][1] = x;
		B[1][1] = a, B[1][2] = b, B[1][3] = c;
		B[2][1] = B[3][2] = 1;
			
		n -= 2;
		
		while(n)
		{
			if(n%2)
			{
				for(i = 1; i <= 3; ++i)
					for(j = 1; j <= 3; ++j)
						for(k = 1; k <= 3; ++k)
							C[i][j] += A[k][j] * B[i][k], C[i][j] %= MOD;
						
				for(i = 1; i <= 3; ++i)
					for(j = 1; j <= 3; ++j)
						A[i][j] = C[i][j], C[i][j] = 0;
			}
			
			for(i = 1; i <= 3; ++i)
				for(j = 1; j <= 3; ++j)
					for(k = 1; k <= 3; ++k)
						C[i][j] += B[i][k] * B[k][j], C[i][j] %= MOD;
					
			for(i = 1; i <= 3; ++i)
				for(j = 1; j <= 3; ++j)
					B[i][j] = C[i][j], C[i][j] = 0;
				
			n /= 2;
		}
		
		fprintf(g, "%lld\n", A[1][1]);
		--t;
	}
	
	fclose(f);
	
	fclose(g);
	
	return 0;
}