#include<fstream>
using namespace std;
int main()
{
	ifstream in("iepuri.in");
	ofstream out("iepuri.out");
	long t,x,j,y,z,a,b,c,w,i,n;
	in>>t;
	for (j=1;j<=t;j++)
	{in>>x>>y>>z>>a>>b>>c>>n;
	w=z*a+y*b+x*c;
	x=y;
	y=z;
	z=w;
	if (z>=666013) z=z%666013;
	w=z*a+y*b+x*c;
	x=y;
	y=z;
	z=w;
	if (z>=666013) z=z%666013;
	for (i=1;i<=n-4;i++)
	{w=2*w-x*c;
	x=y;
	y=z;
	z=w;
	if (z>=666013) z=z%666013;}
	out<<z<<endl;}
	in.close();
	out.close();
	return 0;
}