#include <stdio.h>
typedef long long tipus;
tipus t,x,y,z,a,b,c,n,m=666013;
void masol(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 szoroz(tipus a[4][4],tipus b[4][4]){
int i,j,k;
tipus c[4][4],d[4][4];
masol(a,c);
masol(b,d);
for(i=1;i<=3;i++)for(j=1;j<=3;j++)b[i][j]=0;
for(i=1;i<=3;i++){
for(j=1;j<=3;j++){
for(k=1;k<=3;k++){
b[i][j]=(b[i][j]+(c[i][k]*d[k][j])%m)%m;
}
}
}
}
void hatvany(tipus a[4][4],tipus k){
if(k==1){
}else{
if(k%2==0){
szoroz(a,a);
hatvany(a,k/2);
}else{
tipus c[4][4];
masol(a,c);
szoroz(a,a);
hatvany(a,(k-1)/2);
szoroz(c,a);
}
}
}
int main(){
freopen("iepuri.in","r",stdin);
freopen("iepuri.out","w",stdout);
scanf("%lld",&t);
tipus aa[4][4],i,temp;
for(i=1;i<=t;i++){
scanf("%lld %lld %lld %lld %lld %lld %lld",&x,&y,&z,&a,&b,&c,&n);
aa[1][1]=0;aa[1][2]=0;aa[1][3]=c;
aa[2][1]=1;aa[2][2]=0;aa[2][3]=b;
aa[3][1]=0;aa[3][2]=1;aa[3][3]=a;
hatvany(aa,n-2);
temp=(((x*aa[1][3])%m+(y*aa[2][3])%m)%m+(z*aa[3][3])%m)%m;
printf("%lld\n",temp);
}
return 0;
}