#include<stdio.h>

#define MOD 666013

typedef int matrice[3][3];

int t,x,y,z,a,b,c,n,i,j,k;
matrice m,m_pow_n;

void copymatrice(matrice &a1,matrice a2) {
  for(i=0;i<3;i++)
   for(j=0;j<3;j++) a1[i][j]=a2[i][j];
}

void inmulteste(matrice a,matrice b,matrice &c) {
  matrice a1,a2;
  copymatrice(a1,a);
  copymatrice(a2,b);
  for(i=0;i<3;i++)
   for(j=0;j<3;j++) {
     c[i][j]=0;
     for(k=0;k<3;k++) {
       c[i][j]+=a1[i][k]*a2[k][j];
       c[i][j]%=MOD;
     }
   }
}

void pow(matrice &a,int n) {
  if(n==0) {
    a[0][0]=a[1][1]=a[2][2]=1;
    a[0][1]=a[0][2]=a[1][0]=a[1][2]=a[2][0]=a[2][1]=0;
  }
  else
   if(n%2) {
     pow(a,n-1);
     inmulteste(m,a,a);
   }
   else {
     pow(a,n/2);
     inmulteste(a,a,a);
   }
}

int main() {
  freopen("iepuri.in","r",stdin);
  freopen("iepuri.out","w",stdout);
  m[0][1]=m[1][2]=1;
  scanf("%d",&t);
  while(t--) {
    scanf("%d %d %d %d %d %d %d",&x,&y,&z,&a,&b,&c,&n);
    m[2][0]=c;
    m[2][1]=b;
    m[2][2]=a;
    pow(m_pow_n,n-2);
    printf("%d\n",(m_pow_n[2][0]*x+m_pow_n[2][1]*y+m_pow_n[2][2]*z)%MOD);
  }
  return 0;
}