#include<fstream>
#define Mod 666013
using namespace std;
ifstream fi("iepuri.in");
ofstream fo("iepuri.out");
int t,T,x,y,z,a,b,c,n,i,c1,c2;
int main()
{
	fi>>T;
	for(t=1; t<=T; t++)
	{
		fi>>x>>y>>z>>a>>b>>c>>n;
		for(i=3; i<=n; i++)
		{
			x=((z*a)%Mod+(y*b)%Mod+(x*c)%Mod)%Mod;
			c1=y;
			y=z;
			c2=x;
			x=c1;
			z=c2;
		}
		fo<<z%Mod<<"\n";
	}
	fi.close();
	fo.close();
	return 0;
}