#include<fstream>
#define MODULO 666013

using namespace std;

ifstream in("iepuri.in");
ofstream out("iepuri.out");

const short MAX = 3;

int T, k, A, B, C, i, N;

long long v[MAX];

int main()
{
	in>>T;
	for(k=1; k<=T; k++)
	{
		in>>v[1]>>v[2]>>v[3];//v[1],v[2],v[3]--->v[3]
		in>>A>>B>>C>>N;
		for(i=3; i<=N; i++)
		{
			v[0]=v[1], v[1]=v[2], v[2]=v[3];
			v[3]=(A*v[2])%MODULO;
			v[3]=v[3]+((B*v[1])%MODULO);
			v[3]=v[3]+((C*v[0])%MODULO);
			v[3]=v[3]%MODULO;
		}
		out<<v[3]<<'\n';
	}
	in.close();
	out.close();
	return 0;
}