#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;}