#include <iostream>
#define MOD 666013

using namespace std;

typedef long long tipus;


tipus t;
tipus a[4][4];


void cop(tipus a[4][4],tipus b[4][4]){
	int i,j;
	
	for(i=1;i<=3;i++){
		for(j=1;j<=3;j++)
			b[i][j]=a[i][j];
		
	}
	
}


void mult(tipus a[4][4],tipus b[4][4]){
	
	int i,j,k;
	tipus c[4][4],d[4][4];
	
	cop(a,c);
	cop(b,d);
	

	for(i=1;i<=3;i++)
		for(j=1;j<=3;j++)
			a[i][j]=0;
	
		for(i=1;i<=3;i++)
			for(j=1;j<=3;j++)
				for(k=1;k<=3;k++)
					a[i][j]=(a[i][j]+(c[i][k]*d[k][j])%MOD)%MOD;
	
	
}



void expo(tipus k){
	
	if(k>1)
		if(k%2==0){
			
			expo(k/2);
			
			mult(a,a);
			
		}else{
			
			tipus b[4][4];
			
			cop(a,b);
			
			expo((k-1)/2);
			
			mult(a,a);
			mult(a,b);
			
		}
	
}


int main(){
	freopen("iepuri.in","r",stdin);
	freopen("iepuri.out","w",stdout);
	
	
	int k;
	tipus temp,aa,bb,cc,xx,yy,zz,nn;
	
	scanf("%lld",&t);
	
	for(k=1;k<=t;k++){
		
	scanf("%lld %lld %lld %lld %lld %lld %lld",&xx,&yy,&zz,&aa,&bb,&cc,&nn);
	
	if(nn<3){
		if(nn==0)printf("%lld",xx);
		else
			if(nn==1)printf("%lld",yy);
		else
			printf("%lld",zz);
	}
	else{
		
	a[1][1]=aa;a[1][2]=1;a[1][3]=0;
	a[2][1]=bb;a[2][2]=0;a[2][3]=1;
	a[3][1]=cc;a[3][2]=0;a[3][3]=0;
	
	expo(nn-2);
	
	temp=0;
	
	temp=(zz*a[1][1])%MOD;
	temp=(((yy*a[2][1])%MOD)+temp)%MOD;
	temp=(((xx*a[3][1])%MOD)+temp)%MOD;
	
	printf("%lld\n",temp);}
	
	}
	
	return 0;}