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