#include<cstdio>
#define mod 666013
long long m[4][4],cm[4][4],aux[4][4],mat[4][4],aux2[4][4];
long long inmult(long long a[][4],long long b[][4]){
long long i,j,e;
for(i=1;i<=3;i++)
for(j=1;j<=3;j++)
aux[i][j]=a[i][j],aux2[i][j]=b[i][j],a[i][j]=0;
for(i=1;i<=3;i++)
for(j=1;j<=3;j++){
for(e=1;e<=3;e++)
a[i][j]=(a[i][j]+1LL*aux[i][e]*aux2[e][j])%mod;}}
long long pow(long long e){
while(e){
if (e%2==1){
inmult(m,cm);
e--;}
inmult(cm,cm);
e=e/2;}}
int main(){
freopen("iepuri.in","r",stdin);
freopen("iepuri.out","w",stdout);
long long t,i1,n,x,y,z,a,b,c,i,j,e;
scanf("%lld",&t);
for(i1=1;i1<=t;i1++){
scanf("%lld%lld%lld%lld%lld%lld%lld",&x,&y,&z,&a,&b,&c,&n);
m[1][1]=0;
m[1][2]=1;
m[1][3]=0;
m[2][1]=0;
m[2][2]=0;
m[2][3]=1;
m[3][1]=c;
m[3][2]=b;
m[3][3]=a;
cm[1][1]=0;
cm[1][2]=1;
cm[1][3]=0;
cm[2][1]=0;
cm[2][2]=0;
cm[2][3]=1;
cm[3][1]=c;
cm[3][2]=b;
cm[3][3]=a;
pow(n-1);
mat[1][1]=x;
mat[2][1]=y;
mat[3][1]=z;
for(i=1;i<=3;i++)
for(j=1;j<=3;j++)
aux[i][j]=m[i][j],m[i][j]=0;
j=1;
for(i=1;i<=3;i++){
for(e=1;e<=3;e++)
m[i][j]=(m[i][j]+1LL*aux[i][e]*mat[e][j])%mod;}
printf("%lld\n",m[1][1]);}
return 0;}