#include<stdio.h>
#include<string.h>
#define mod 666013

long long int a[4][4],b[4][4],c[4][4],n,t,i;
void multi(long long int sol[4][4],long long int a[4][4],long long int b[4][4])
{long long int rez[4][4],i,j;
for(i = 1 ; i <= 3 ; i++)
	for(j = 1; j<= 3 ; j++)
		{rez[i][j] = a[i][1]*b[1][j] ;
		rez[i][j] +=a[i][2]*b[2][j] ;
		rez[i][j] += a[i][3]*b[3][j];
		if(rez[i][j] > mod)rez[i][j] = rez[i][j]%mod;
		}
memcpy(sol,rez,sizeof(rez));

}

void solve(){
	memset(b,0,sizeof(b));
	a[1][2] = 1;
	a[2][3] = 1;
	b[1][1] = b[2][2] = b[3][3] = 1;
	while(n)
		{if(n%2)multi(b,b,a);
		multi(a,a,a);
		n = n>>1;
		}
	multi(c,b,c);
/*int i;	
for(i=1;i<=n;i++)
	multi(c,a,c);*/
}


void citire(){
freopen("iepuri.in","r",stdin);
freopen("iepuri.out","w",stdout);
scanf("%lld",&t);
for(i = 1 ;i <= t ;i++)
	{memset(a,0,sizeof(a));
	memset(c,0,sizeof(c));
	scanf("%lld %lld %lld %lld %lld %lld %lld",&c[1][1],&c[2][1],&c[3][1],&a[3][3],&a[3][2],&a[3][1],&n);
	solve();
	printf("%lld\n",c[1][1]);
	}

}

int main(){
citire();

return 0;}