#include <algorithm>
#include <stdio.h>

#define restRez 666013

using namespace std;

long long matCalc[4][4];
long long testCases;

void inmultesteMatrice(long long (&matProdus)[4][4], long long matFact[4][4])
{
	long long matTemp[4][4];
	memset(matTemp, 0, sizeof(matTemp));
	
	for (int i = 1; i <= 3; i++)
		for (int j = 1; j <= 3; j++)
			for (int k = 1; k <= 3; k++)
				matTemp[i][j] = (matTemp[i][j] + matProdus[i][k] * matFact[k][j]) % restRez;
			
	memcpy(matProdus, matTemp, sizeof(matProdus));
}

void ridica(long long (&matCalc)[4][4], int x)
{
	long long r[4][4];
	memset(r, 0, sizeof(r));
	r[1][1] = r[2][2] = r[3][3] = 1;
	
	for (; x > 1; x /= 2)
	{
		if (x & 1)
			inmultesteMatrice(r, matCalc);
		
		inmultesteMatrice(matCalc, matCalc);
	}
	
	inmultesteMatrice(matCalc, r);
}	

int main()
{
	freopen("iepuri.in", "r", stdin);
	freopen("iepuri.out", "w", stdout);
	
	
	for (scanf("%d", &testCases); testCases; testCases--)
	{
		long long x, y, z, n;
		memset(matCalc, 0, sizeof(matCalc));
		matCalc[1][2] = matCalc[2][3] = 1;
		
		scanf("%lld %lld %lld", &x, &y, &z);
		scanf("%lld %lld %lld", &matCalc[3][3], &matCalc[3][2], &matCalc[3][1]);
		scanf("%lld", &n);
		
		ridica(matCalc, n);
		
		long long sol = (matCalc[1][1] * x) % restRez + (matCalc[1][2] * y) % restRez + (matCalc[1][3] * z) % restRez;
		
		printf("%lld\n", sol % restRez);		
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}