#include <fstream>
#include <cstring>
#define MOD 666013
using namespace std;

int T,N;
long long V[4],Tmp[4],A[4][4],Tmp2[4][4];


void ExpLog(int P) {
	
	int i,j,k;
	
	while(P) {
		
		if(P&1) {
			
			for(i=1;i<=3;i++)
				for(k=1;k<=3;k++)
					Tmp[i]=(Tmp[i]+V[k]*A[i][k])%MOD;
				
			memcpy(V,Tmp,sizeof(V));
			memset(Tmp,0,sizeof(Tmp));
			}
		
		for(i=1;i<=3;i++)
			for(j=1;j<=3;j++)
				for(k=1;k<=3;k++)
					Tmp2[i][j]=(Tmp2[i][j]+A[i][k]*A[k][j])%MOD;
		
		memcpy(A,Tmp2,sizeof(A));
		memset(Tmp2,0,sizeof(Tmp2));
		
		P>>=1;
		}

}
int main() {
	
	ifstream in("iepuri.in");
	ofstream out("iepuri.out");
	in>>T;
	
	while(T--) {
		
		in>>V[3]>>V[2]>>V[1];
		in>>A[1][1]>>A[1][2]>>A[1][3]>>N;
		A[2][2]=A[2][3]=A[3][1]=A[3][3]=0;
		A[2][1]=A[3][2]=1;
		
		ExpLog(N-2);
		
		out<<V[1]<<'\n';
		}
	
	in.close();
	out.close();
	
	return 0;
	
}