//Iepuri
#include<stdio.h>

const long long N=3, M=1, MOD=666013;

long long t, v[N][M], r[N][M], m[N][N], s[N][N];

void Initialise()
{
	scanf("%lld%lld%lld",&v[0][0],&v[1][0],&v[2][0]);
	scanf("%lld%lld%lld",&s[2][2],&s[2][1],&s[2][0]);
	
	s[0][1]=s[1][2]=1;
	s[0][0]=s[0][2]=s[1][0]=s[1][1]=0;
	
	for( long long i=0; i<N; ++i)
		for( long long j=0; j<N; ++j)
			m[i][j]= (i==j) ? 1:0;
}

void Multiply( long long a[N][N], long long b[N][N])
{
	long long c[N][N];
	for( long long i=0; i<N; ++i)
		for( long long j=0; j<N; ++j)
		{
			c[i][j]=0;
			for( long long k=0; k<N; ++k)
				c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MOD;
		}
	for( long long i=0; i<N; ++i)
		for( long long j=0; j<N; ++j)
			a[i][j]=c[i][j]%MOD;
}

void Resolve(long long n)
{
	while(n)
	{
		if(n&1)
			Multiply(m,s);
		n>>=1;
		Multiply(s,s);
	}
}

int main()
{
	freopen("iepuri.in","r",stdin);
	freopen("iepuri.out","w",stdout);
	
	scanf("%lld",&t);
	while(t--)
	{
		long long n;
		Initialise();
		scanf("%lld",&n);
		Resolve(n);
		long long rez=(v[0][0]*m[0][0])%MOD;
		rez=(rez+v[1][0]*m[0][1])%MOD;
		rez=(rez+v[2][0]*m[0][2])%MOD;
		printf("%lld\n",rez);
	}
	
	return 0;
}