#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;
  long long a, b, c, x, y, z;
  fscanf(fin, "%d", &n);
  for(p=1; p<=n; p++){
    fscanf(fin, "%I64d%I64d%I64d%I64d%I64d%I64d%d", &x, &y, &z, &a, &b, &c, &nrzile);
    for(f=1; f<=3; f++)
      for(j=1; j<=3; j++)
        rez[f][j]=rezc[f][j]=i[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){
        rez[1][1]=rezc[1][1]*i[1][1]+rezc[1][2]*i[2][1]+rezc[1][3]*i[3][1];
        rez[1][2]=rezc[1][1]*i[1][2]+rezc[1][2]*i[2][2]+rezc[1][3]*i[3][2];
        rez[1][3]=rezc[1][1]*i[1][3]+rezc[1][2]*i[2][3]+rezc[1][3]*i[3][3];

        rez[2][1]=rezc[2][1]*i[1][1]+rezc[2][2]*i[2][1]+rezc[2][3]*i[3][1];
        rez[2][2]=rezc[2][1]*i[1][2]+rezc[2][2]*i[2][2]+rezc[2][3]*i[3][2];
        rez[2][3]=rezc[2][1]*i[1][3]+rezc[2][2]*i[2][3]+rezc[2][3]*i[3][3];

        rez[3][1]=rezc[3][1]*i[1][1]+rezc[3][2]*i[2][1]+rezc[3][3]*i[3][1];
        rez[3][2]=rezc[3][1]*i[1][2]+rezc[3][2]*i[2][2]+rezc[3][3]*i[3][2];
        rez[3][3]=rezc[3][1]*i[1][3]+rezc[3][2]*i[2][3]+rezc[3][3]*i[3][3];

        k--;
      }
      else{
        k/=2;
        i[1][1]=ic[1][1]*ic[1][1]+ic[1][2]*ic[2][1]+ic[1][3]*ic[3][1];
        i[1][2]=ic[1][1]*ic[1][2]+ic[1][2]*ic[2][2]+ic[1][3]*ic[3][2];
        i[1][3]=ic[1][1]*ic[1][3]+ic[1][2]*ic[2][3]+ic[1][3]*ic[3][3];

        i[2][1]=ic[2][1]*ic[1][1]+ic[2][2]*ic[2][1]+ic[2][3]*ic[3][1];
        i[2][2]=ic[2][1]*ic[1][2]+ic[2][2]*ic[2][2]+ic[2][3]*ic[3][2];
        i[2][3]=ic[2][1]*ic[1][3]+ic[2][2]*ic[2][3]+ic[2][3]*ic[3][3];

        i[3][1]=ic[3][1]*ic[1][1]+ic[3][2]*ic[2][1]+ic[3][3]*ic[3][1];
        i[3][2]=ic[3][1]*ic[1][2]+ic[3][2]*ic[2][2]+ic[3][3]*ic[3][2];
        i[3][3]=ic[3][1]*ic[1][3]+ic[3][2]*ic[2][3]+ic[3][3]*ic[3][3];
      }
      rez[1][1]%=MOD; rez[1][2]%=MOD; rez[1][3]%=MOD;
      rez[2][1]%=MOD; rez[2][2]%=MOD; rez[2][3]%=MOD;
      rez[3][1]%=MOD; rez[3][2]%=MOD; rez[3][3]%=MOD;

      i[1][1]%=MOD; i[1][2]%=MOD; i[1][3]%=MOD;
      i[2][1]%=MOD; i[2][2]%=MOD; i[2][3]%=MOD;
      i[3][1]%=MOD; i[3][2]%=MOD; i[3][3]%=MOD;

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

      ic[1][1]=i[1][1]; ic[1][2]=i[1][2]; ic[1][3]=i[1][3];
      ic[2][1]=i[2][1]; ic[2][2]=i[2][2]; ic[2][3]=i[2][3];
      ic[3][1]=i[3][1]; ic[3][2]=i[3][2]; ic[3][3]=i[3][3];
    }
//    for(f=1; f<=3; f++){
//      for(j=1; j<=3; j++)
//        printf("%d ", rez[f][j]);
//      printf("\n");
//    }
    fprintf(fout, "%I64d\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;
}