#include<iostream>
#include<fstream>
#define rest 666013
using namespace std;
ifstream f("iepuri.in");
ofstream g("iepuri.out");
long long int t,x,y,z,a,b,c,n;
long long int A[2][4], B[4][2];
void inmultire(long long int A[2][4],long long int B[4][2]){
	int s=((A[1][3]*B[1][1])%rest+(A[1][2]*B[2][1])%rest+(A[1][1]*B[3][1])%rest)%rest;
	A[1][1]=A[1][2];
	A[1][2]=A[1][3];
	A[1][3]=s;
}
int main(){
	f>>t;
	for(int i=1;i<=t;++i){
	f>>x>>y>>z>>a>>b>>c>>n;
	A[1][1]=x,A[1][2]=y,A[1][3]=z,B[1][1]=a,B[2][1]=b,B[3][1]=c;
	for(int i=1;i<=n-2;++i)
		inmultire(A,B);
	
	g<<A[1][3]<<"\n";
	}
	return 0;
}