#include<iostream>
#include<fstream>
using namespace std;

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

const int MOD=666013;
int main(){
long long T,x,y,z,a,b,c,n,i,nr,j;

in>>T;
for(i=1;i<=T;i++){
	in>>x>>y>>z>>a>>b>>c>>n;
	nr=a*z+b*y+c*x;
		for(j=3;j<=n;j++){
			x=y;
			y=z;
			z=nr;
			nr=a*z+b*y+c*x;
		}
	out<<z%MOD<<"\n";
}

return 0;
}