#include <bits/stdc++.h>
#define INFILE "iepuri.in"
#define OUTFILE "iepuri.out"
using namespace std;
const long long sz=3;
const long long MOD=666013;
ifstream in(INFILE);
ofstream out(OUTFILE);
typedef array<array<long long,sz>,sz> Mat;

void Init(Mat&a){
  for(long long i=0;i<sz;i++){
    for(long long j=0;j<sz;j++){
      a[i][j]=0;
    }
  }
}
Mat operator*(Mat a,Mat b){
  Mat c;
  for(long long i=0;i<sz;i++){
    for(long long j=0;j<sz;j++){
      long long s=0;
      for(long long k=0;k<sz;k++){
        s=s+a[i][k]*b[k][j];
        s=s%MOD;
      }
      c[i][j]=s;
    }
  }
  return c;
}
ostream& operator<<(ostream&os,Mat&a){
  for(long long i=0;i<sz;i++){
    for(long long j=0;j<sz;j++){
      os<<setw(2)<<a[i][j]<<" ";
    }
    os<<"\n";
  }
  os<<"\n";
  return os;
}

Mat putereLog(Mat a,long long ex){
  Mat rasp;
  Init(rasp);
  rasp[0][0]=rasp[1][1]=rasp[2][2]=1;
//  cout<<rasp;
  while(ex>0){
    if(ex%2==1){
      ex--;
      rasp=rasp*a;
    }
    a=a*a;
    ex/=2;
  }
  return rasp;
}
void InitFib(Mat&a,long long A,long long B,long long C){
  Init(a);
  a[0][0]=A;
  a[0][1]=B;
  a[0][2]=C;
  a[1][0]=1;
  a[2][1]=1;
}
void Determinare(long long X,long long Y,long long Z,long long A,long long B,long long C,long long N){
  if(N<=2){
    if(N==0)
      out<<X<<"\n";
    else if(N==1)
      out<<Y<<"\n";
    else
      out<<Z<<"\n";
    return;
  }
  Mat a;
  N++;
  InitFib(a,A,B,C);
  a=putereLog(a,N-3);
  //cout<<a;
  long long t1=(Z*a[0][0])%MOD;
  long long t2=(Y*a[0][1])%MOD;
  long long t3=(X*a[0][2])%MOD;
  long long Fib=(t1+t2+t3)%MOD;
  out<<Fib<<"\n";
}

int main(){
  long long t;
  in>>t;
  for(long long i=1;i<=t;i++){
    long long X,Y,Z,A,B,C,N;
    in>>X>>Y>>Z>>A>>B>>C>>N;
    Determinare(X,Y,Z,A,B,C,N);
  }
  return 0;
}