#include<stdio.h>   
#define DIM 666013   
long long t[4][4],w[4][4],m[4][4],n1;   
void calc(long x){   
  int i,j;   
  long long p;   
  if(x%2==1)   
    for(i=1;i<=3;i++)   
      for(j=1;j<=3;j++)   
    t[i][j]=m[i][j];   
  else {   
    t[1][2]=0;   
    t[1][3]=0;   
    t[2][1]=0;   
    t[2][3]=0;   
    t[3][1]=0;   
    t[3][2]=0;   
    t[1][1]=1;   
    t[2][2]=1;   
    t[3][3]=1;   
  }   
  for(p=2;p<=x;p*=2){   
    for(i=1;i<=3;i++)   
      for(j=1;j<=3;j++)   
    w[i][j]=((m[i][1]*m[1][j])%DIM+(m[i][2]*m[2][j])%DIM +(m[i][3]*m[3][j])%DIM)%DIM;   
    for(i=1;i<=3;i++)   
      for(j=1;j<=3;j++)   
    m[i][j]=w[i][j];   
    if(x & p){   
      for(i=1;i<=3;i++)   
    for(j=1;j<=3;j++)   
      w[i][j]=((t[i][1]*m[1][j])%DIM+(t[i][2]*m[2][j])%DIM+(t[i][3]*m[3][j])%DIM)%DIM;   
      for(i=1;i<=3;i++)   
    for(j=1;j<=3;j++)   
      t[i][j]=w[i][j];   
    }   
  }   
  
}   
  
  
void solve(){   
  int i,tst,x,y,z,a,b,c;   
  long n;   
  FILE *f,*g;   
  f=fopen("iepuri.in","r");   
  g=fopen("iepuri.out","w");   
  fscanf(f,"%d",&tst);   
  for(i=1;i<=tst;i++){   
    fscanf(f,"%d %d %d %d %d %d %ld",&x,&y,&z,&a,&b,&c,&n);   
    m[1][1]=0;   
    m[1][2]=1;   
    m[1][3]=0;   
    m[2][1]=0;   
    m[2][2]=0;   
    m[2][3]=1;   
    m[3][1]=c;   
    m[3][2]=b;   
    m[3][3]=a;   
    calc(n);   
    n1=(t[1][1]*x+t[1][2]*y+t[1][3]*z)%DIM;   
    fprintf(g,"%lld\n",n1);   
  }   
  fclose(f);   
  fclose(g);   
}   
int main()   
{   
  solve();   
  return 0;   
}