#include<fstream.h>
ofstream out("iepuri.out");
const int k=666013;
int x,y,z,a,b,c,sol,t;
long n;
int rest(int n,int p)
{	int s=0,i,a;
	a=n;
	for(i=0;(1<<i)<=p;i++)
	{	if( ( (1<<i)  & p )>0 )
			s=(s+a)%k;

			a=(a+a)%k;
	}
	return s;
}
int calcul()
{	sol=sol+rest(x,c);
	sol=sol+rest(y,b);
	sol=sol+rest(z,a);
	return sol;
}
int main()
{       int temp=0,j;
	long i;
	ifstream in("iepuri.in");
	in>>t;
	for(j=1;j<=t;j++)
	{       sol=0;temp=0;
		in>>x>>y>>z>>a>>b>>c>>n;
		for(i=1;i<=n-2;i++)
		{       sol=0;
			temp=calcul();
			x=y;y=z;z=temp;
		}
		out<<sol<<endl;

	}
	in.close();
	out.close();
	return 0;
}