#include<fstream>
#define dim 20000002
#define modulo 666013
using namespace std;

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

int d[dim],n;
int a,b,c,t;

void rezolva()
{
	int i;
	for(i=3;i<=n;i++)
		d[i]=((d[i-1]%modulo)*a+(d[i-2]%modulo)*b+(d[i-3]%modulo)*c)%modulo;
	g<<d[n]<<"\n";
}

void citire()
{
	
	int i;
	f>>t;
	for(i=1;i<=t;i++)
	{
		f>>d[0]>>d[1]>>d[2]>>a>>b>>c>>n;
		rezolva();
		//g<<d[0]<<" "<<d[1]<<" "<<d[2]<<" "<<a<<" "<<b<<" "<<c<<" "<<n<<"\n";
	}
	
}


int main()
{
	citire();
	return 0;
}