#include<fstream>
using namespace std;
unsigned long long a,b,c,n,x,y,z,a1[5],nr,t,i,j,k,l;
int main()
{
	ifstream f("iepuri.in");
	ofstream g("iepuri.out");
	f>>t;
	for(l=1;l<=t;l++)
	{
		f>>x>>y>>z>>a>>b>>c>>n;
		a1[1]=x;
		a1[2]=y;
		a1[3]=z;
		
		for(i=3;i<=n;i++)
		{
			nr=0;
			nr=a1[3]*a+a1[2]*b+a1[1]*c;
			a1[1]=a1[2];
			a1[2]=a1[3];
			a1[3]=nr;
		}
		while(a1[3]>=666013)
			a1[3]-=666013;
			g<<a1[3]<<"\n";
		
	}
	return 0;
}