#include <stdio.h>
#include <stdlib.h>
#define MOD 666013

long long rez[5][5], i[5][5], ic[5][5], rezc[5][5];
int main(){
  FILE*fin=fopen("iepuri.in", "r");
  FILE*fout=fopen("iepuri.out", "w");
//  x y z -> y z a*x+b*y+c*z
//  0 0 c
//  1 0 b
//  0 1 a
//1 zi-x
//2 zi-y
//3 zi-z
  int n, j, p, nrzile, f, k, s, pr;
  long long a, b, c, x, y, z;
  fscanf(fin, "%d", &n);
  for(pr=1; pr<=n; pr++){
    printf("%d", pr);
    fscanf(fin, "%lld%lld%lld%lld%lld%lld%d", &x, &y, &z, &a, &b, &c, &nrzile);
    for(f=1; f<=3; f++)
      for(j=1; j<=3; j++)
        rez[f][j]=i[f][j]=rez[f][j]=ic[f][j]=0;

    i[2][1]=i[3][2]=1;
    i[1][3]=c; i[2][3]=b; i[3][3]=a;

    ic[2][1]=ic[3][2]=1;
    ic[1][3]=c; ic[2][3]=b; ic[3][3]=a;

    rez[1][1]=rez[2][2]=rez[3][3]=1;

    rezc[1][1]=rezc[2][2]=rezc[3][3]=1;

    k=nrzile-2;
//    printf("%d\n", k);
    while(k>0){
      if(k%2==1){
        for(f=1; f<=3; f++)
          for(j=1; j<=3; j++){
            s=0;
            for(p=1; p<=3; p++)
              s=s+rezc[f][p]*i[p][j];

            rez[f][j]=s;
//            if(f==3 && j==3)
//              printf("%d\n", s);
//            printf("%d", s);
          }

        k--;
      }
      else{
        k/=2;
        for(f=1; f<=3; f++)
          for(j=1; j<=3; j++){
            s=0;
            for(p=1; p<=3; p++)
              s=s+ic[f][p]*ic[p][j];

            i[f][j]=s;
          }
      }
//      printf("%d\n", k);
//      for(f=1; f<=3; f++){
//        for(j=1; j<=3; j++)
//          printf("%d ", rez[f][j]);
//        printf("\n");
//      }
//      printf("\n");
//      for(f=1; f<=3; f++){
//        for(j=1; j<=3; j++)
//          printf("%d ", i[f][j]);
//        printf("\n");
//      }
//      printf("\n\n\n");
      for(f=1; f<=3; f++)
        for(j=1; j<=3; j++){
          rez[f][j]%=MOD;
          rezc[f][j]=rez[f][j];
          i[f][j]%=MOD;
          ic[f][j]=i[f][j];
        }
    }
//    for(f=1; f<=3; f++){
//      for(j=1; j<=3; j++)
//        printf("%d ", rez[f][j]);
//      printf("\n");
//    }
//    printf("DA");
    fprintf(fout, "%lld\n", (x*rez[1][3]%MOD+y*rez[2][3]%MOD+z*rez[3][3]%MOD)%MOD);
//    printf("%d %d %d", x*rez[1][3], y, z);
  }
  return 0;
}