#include<fstream>
using namespace std;
ifstream in("iepuri.in");
ofstream out("iepuri.out");
long long x,y,z,a,b,c,n,t,nr=666013,cautat,ziua=3;
main()
{
in>>t;
for(long long i=1;i<=t;i++)
{
	in>>x;in>>y;in>>z;in>>a;in>>b;in>>c;in>>n;
	while(ziua<=n)
	{
		cautat=a*z+b*y+c*x;
		x=y;
		y=z;
		z=cautat;
		ziua++;
	}
	out<<cautat%nr<<'\n';
	ziua=3;
	cautat=0;
}
in.close();
out.close();
}