#include<stdio.h>
#include<string.h>
const int mod=666013;
int a[3][3]={{0,1,0},{0,0,1},{0,0,0}};
int b[3][3],A,B,C,x,y,z,n,t,i,j,k,c[3][3];
void putere(int n)
{if(n==1) {memcpy(b,a,sizeof(a)); return;}
 putere(n/2);

 memset(c,0,sizeof(c));
 for(i=0;i<=2;i++)
  for(j=0;j<=2;j++)
   for(k=0;k<=2;k++)
    c[i][j]=(c[i][j]+b[i][k]*b[k][j])%mod;

 memcpy(b,c,sizeof(b));
 if(n%2==0) return;
 
 memset(c,0,sizeof(c));
 for(i=0;i<=2;i++)
  for(j=0;j<=2;j++)
   for(k=0;k<=2;k++)
    c[i][j]=(c[i][j]+b[i][k]*a[k][j])%mod;

 memcpy(b,c,sizeof(b));
}
int main()
{freopen("iepuri.in","r",stdin);
 freopen("iepuri.out","w",stdout);
 scanf("%d",&t);
 for(;t;t--){
 scanf("%d %d %d %d %d %d %d",&x,&y,&z,&A,&B,&C,&n);
 a[2][0]=C;
 a[2][1]=B;
 a[2][2]=A;
 if(n==0){ printf("%d\n",x);  continue;} 
 if(n==1){ printf("%d\n",y);  continue;}
 if(n==2){ printf("%d\n",z);  continue;}
 putere(n-2);
 printf("%d\n",(x*b[2][0]+y*b[2][1]+z*b[2][2])%mod);}
 fclose(stdout);
 return 0;}