//Iepuri
#include<stdio.h>

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

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

void Initialise()
{
	scanf("%d%d%d",&v[0][0],&v[1][0],&v[2][0]);
	scanf("%d%d%d",&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( int i=0; i<N; ++i)
		for( int j=0; j<N; ++j)
			m[i][j]= (i==j) ? 1:0;
}

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

void Resolve(int 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("%d",&t);
	while(t--)
	{
		int n;
		Initialise();
		scanf("%d",&n);
		Resolve(n);
		int 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("%d\n",rez);
	}
	
	return 0;
}