#include<iostream>
#include<fstream>
using namespace std;
int t;
int debug=0;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
long int x,y,z,a,b,c,n,zi1,zi2,zi4,zi0;
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;
	zi0=x;zi1=y;zi2=z;
	for(int i=3;i<=n;i++)
	{
		zi4=c*zi0+b*zi1+1*zi2;
		zi0=zi1;
		zi1=zi2;zi2=zi4;
	}
	fout<<modulo(zi4);debug++;
	if(debug!=t) fout<<endl;
	
	
}



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