#include <fstream>
#include <string.h>
using namespace std;
int a[4][4],b[4][4],c[4][4];
int h=666013;
void inmul(int e[4][4],int 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]%666013;
}
		

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];
	int n;
	fin>>n;
	n-=2;
	a[2][1]=1;
	a[3][2]=1;
	int p;
	for(p=n;p;p=p>>1)
	{	
		if(p&1)inmul(a,b);
		inmul(a,a);
	}
	fout<<b[1][1]<<"\n";
		
	}	
}