#include<stdio.h>  
 #include<string.h>  
 int mod=666013;  
 long long a[3][3]={{0,1,0},{0,0,1},{0,0,0}};  
 long long 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]+a[i][k]*b[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("%lld\n",(x*b[2][0]+y*b[2][1]+z*b[2][2])%mod);}  
  fclose(stdout);  
  return 0;}