#include <stdio.h>

using namespace std;

#define MOD 666013

struct Matrice{
  long long mat[5][5];
};

Matrice matrez,matbaza,matinit;

Matrice inmultire(Matrice A,Matrice B){
  long long i,j,k;
  Matrice rez;
  for(i=1;i<=3;i++){
    for(j=1;j<=3;j++){
      rez.mat[i][j]=0;
      for(k=1;k<=3;k++){
        rez.mat[i][j]=(rez.mat[i][j]+(A.mat[i][k]*B.mat[k][j])%MOD)%MOD;
      }
    }
  }
  return rez;
}

int main()
{
  FILE *fin,*fout;
  fin=fopen("iepuri.in","r");
  fout=fopen("iepuri.out","w");

  long long T,n,z0,z1,z2,A,B,C,i;
  fscanf(fin,"%lld",&T);
  for(i=0;i<T;i++){
    fscanf(fin,"%lld%lld%lld%lld%lld%lld%lld",&z0,&z1,&z2,&A,&B,&C,&n);
    matbaza.mat[1][1]=matbaza.mat[1][2]=matbaza.mat[2][2]=matbaza.mat[3][1]=0; ///matricea constanta
    matbaza.mat[2][1]=matbaza.mat[3][2]=1;
    matbaza.mat[1][3]=C;
    matbaza.mat[2][3]=B;
    matbaza.mat[3][3]=A;
    matrez.mat[1][1]=matrez.mat[2][2]=matrez.mat[3][3]=1; ///matricea rezultata - o initializam cu mat identitate
    matrez.mat[1][2]=matrez.mat[1][3]=matrez.mat[2][1]=matrez.mat[2][3]=matrez.mat[3][1]=matrez.mat[3][2]=0;
    matinit.mat[1][1]=z0;
    matinit.mat[1][2]=z1;
    matinit.mat[1][3]=z2;
    n--; ///matbaza^n-1
    while(n>0){
      if(n%2==0){
        matbaza=inmultire(matbaza,matbaza);
        n/=2;
      }
      else{
        matrez=inmultire(matrez,matbaza);
        n--;
      }
    }
   matrez=inmultire(matinit,matrez);
   fprintf(fout,"%lld\n",matrez.mat[1][2]);
  }

  fclose(fin);
  fclose(fout);

  return 0;
}