#include <cstdio>
using namespace std;

#define r 666013
#define d 5
short x, y, z, a, b, c;
long long n;
long long m[d][d], M[d][d], MC[d][d];

void init(long long x[][d])
{
	for(short i=1; i<=3; i++)
		for(short j=1; j<=3; j++)
			x[i][j] = 0;
	x[1][2] = x[2][3] = 1; 
	x[3][1] = c; x[3][2] = b; x[3][3] = a;
}

void produs2(long long A[][d], long long B[][d])
{
	for(short k=1; k<=3; k++)
		for(short i=1; i<=3; i++)
			for(short j=1; j<=3; j++)
				MC[k][i] = ( MC[k][i] + A[k][j] * B[j][i])%r;
	for(short i=1; i<=3; i++)
		for(short j=1; j<=3; j++)
		{
			m[i][j] = MC[i][j];
			MC[i][j] = 0;
		}
}	

void produs(long long A[][d], long long B[][d])
{
	for(short k=1; k<=3; k++)
		for(short i=1; i<=3; i++)
			for(short j=1; j<=3; j++)
				MC[k][i] = ( MC[k][i] + A[k][j] * B[j][i])%r;
	for(short i=1; i<=3; i++)
		for(short j=1; j<=3; j++)
		{
			M[i][j] = MC[i][j];
			MC[i][j] = 0;
		}
	/*
	for(short i=1; i<=3; i++)
	{
		for(short j=1; j<=3; j++)
			printf("%ld ", M[i][j]);
		printf("\n");
	}
	printf("\n");
	*/
}

void m_la_n()
{
	while(n)
	{
		if(n%2)
		{
			n--;
			produs(M, m);
		}
		n = n/2;
		produs2(m, m);

	}
}

void afisare()
{	
	long long sol = ( (M[1][1]*x)%r + (M[1][2]*y)%r + (M[1][3]*z)%r )%r;
	printf("%lld\n", sol);
}

void citire()
{
	short T;
	freopen("iepuri.in","r",stdin); scanf("%hd", &T);
	for(; T; T--)
	{
		scanf("%hd %hd %hd %hd %hd %hd %lld", &x, &y, &z, &a, &b, &c, &n);
		n--;
		init(m); init(M);
		//produs(M,M); produs(M,M); produs(M,M);
		m_la_n();
		afisare();
		
	}
}

int main()
{
	freopen("iepuri.out","w",stdout);
	citire(); 
	return 0;
}