#include<fstream>
#define modulo 666013
using namespace std;
ifstream f("search.in");
ofstream g("iepuri.out");
int x,y,z,a,b,c,n;
int t;
int i,j,k;
int zi1,zi2,zi3,zi0;
inline int req(int k)
{
	if(k==1)
		return a*zi2+b*zi3+c*zi0;
	if(k==2)
		return (a*zi1)+(b*zi2)+(c*zi3);
	if(k==3)
		return (a*req(k-1))+(b*zi1)+(c*zi2);
	else
		return (a*req(k-1))+(b*req(k-1))+(c*req(k-3));
}
int main()
{
	f>>t;
	for(i=1;i<=t;i++)
	{
		f>>x>>y>>z>>a>>b>>c>>n;
		zi0=x;
		zi3=y;
		zi2=z;
		zi1=a*zi2+b*zi3+c*zi0;
		g<<req(n-2)%modulo<<"\n";
	}
	return 0;
}