#include <fstream>
#include <string.h> 
using namespace std;
long long a[4][4],b[4][4],c[4][4];
int h=666013;
void inmul(long long e[4][4],long long f[4][4])
{
	int i,j,k;
	memset(c,0,sizeof(c));
	for(i=1;i<=3;i++)
		for(j=1;j<=3;j++)
			for(k=1;k<=3;k++)
				c[i][j]+=((e[i][k]%h)*(f[k][j]%h))%h;
	for(i=1;i<=3;i++)
		for(j=1;j<=3;j++)
			f[i][j]=c[i][j]%h;
}
		

ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
int main()
{	
	int t,l;
	fin>>t;
	for(l=1;l<=t;l++)
	{
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		fin>>b[3][1]>>b[2][1]>>b[1][1];
		fin>>a[1][1]>>a[1][2]>>a[1][3];
		long long n;
		fin>>n;
		n-=2;
		a[2][1]=1;
		a[3][2]=1;
		long long p;
		for(p=n;p;p=p>>1)
		{	
			if(p&1)inmul(a,b);
			inmul(a,a);
		}
		fout<<b[1][1]<<"\n";
		
	}	
}