#include<iostream>
#include<fstream>
using namespace std;
int t;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
long int x,y,z,a,b,c,n;
int modulo(int long x)
{
	long int k=x;
	while(k>=666013) k-=666013;
	return k;
}

void rezolva()
{
	fin>>x>>y>>z>>a>>b>>c>>n;
	long int zi0=x,zi1=y,zi2=z,zi4;
	for(int i=3;i<=n;i++)
	{
		zi4=c*zi0+b*zi1+1*zi2;
		zi0=zi1;
		zi1=zi2;zi2=zi4;
	}
	fout<<modulo(zi4)<<endl;
	
}



int main()
{
	fin>>t;
	for(int i=1;i<=t;i++)
	{
		rezolva();
	}
	
}