#include<stdio.h>
using namespace std;

const long m=666013; 

long long v[3][3],h[3][3],o[3][3];

long t,x,y,z,a,b,c,n;

void inmultire()
{
	long i,j,k;
	for(i=0;i<=2;i++)
		for(j=0;j<=2;j++)
			for(k=0;k<=2;k++)
				h[i][j]=(h[i][j]%m+(v[i][k]*v[k][j])%m)%m;
	for(i=0;i<=2;i++)
		for(j=0;j<=2;j++)
		{	v[i][j]=h[i][j];
			h[i][j]=0;
		}
}
void inmultire2()
{
	long i,j,k;
	for(i=0;i<=2;i++)
		for(j=0;j<=2;j++)
			for(k=0;k<=2;k++)
				h[i][j]=(h[i][j]%m+(v[i][k]*v[k][j])%m)%m;
	
	for(i=0;i<=2;i++)
		for(j=0;j<=2;j++)
			for(k=0;k<=2;k++)
				o[i][j]=(o[i][j]%m+(h[i][k]*v[k][j])%m)%m;
	
	for(i=0;i<=2;i++)
		for(j=0;j<=2;j++)
		{	v[i][j]=o[i][j];
			h[i][j]=0;
			o[i][j]=0;
		}
}
void putere(long n) 
{   if(n==1) ; 
	else if(n%2==0)
		{ 	inmultire();
			putere(n/2);
		}
	else 
	{	inmultire2();
		putere(n/2); 
	}
} 

int main()
{
	freopen("iepuri.in","r",stdin);
	freopen("iepuri.out","w",stdout);
	scanf("%ld",&t);
	for(long g=1;g<=t;g++)
	{
	scanf("%ld%ld%ld%ld%ld%ld%ld",&x,&y,&z,&a,&b,&c,&n);
	long i,j;	
	v[0][0]=a;
	v[0][1]=b;
	v[0][2]=c;
	v[1][0]=1;
	v[2][1]=1;
	putere(n-2);
	long long q=(v[0][0]*z)%m+(v[0][1]*y)%m+(v[0][2]*x)%m;
	printf("%lld\n",q%m);
	q=0;
	for(i=0;i<=2;i++)
		for(j=0;j<=2;j++)
		{	
			v[i][j]=0;
			o[i][j]=0;
			h[i][j]=0;
		}
	
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
	
}