#include<bits/stdc++.h>
using namespace std;
const int NEUTRU=-5;
const int MOD=666013;
struct Matrix{
  vector<vector<int>> mat;
  int n,m;
  Matrix(int _n,int _m,int val){
    n=_n;
    m=_m;
    if(val==NEUTRU){
      mat.resize(n,vector<int>(m,0));
      for(int i=0;i<n;i++)
        mat[i][i]=1;
    }
    else
      mat.resize(n,vector<int>(m,val));
  }
  Matrix (vector<vector<int>> x){
    mat=x;
    n=mat.size();
    m=mat[0].size();
  }
  Matrix mult(Matrix other){
    Matrix ans(n,other.m,0);
    if(m==other.n){
      for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
          for(int k=0;k<other.m;k++){
            ans.mat[i][k]+=(1LL*mat[i][j]*other.mat[j][k])%MOD;
            ans.mat[i][k]%=MOD;
          }
        }
      }

      return ans;
    }
    else
      return ans;
  }
};
Matrix lgcput(Matrix b,int p){
  Matrix ans(b.n,b.m,NEUTRU);
  //ans.mat[0][0]=ans.mat[1][1]=1;
  while(p){
    if(p&1){
      ans=ans.mult(b);
    }
    b=b.mult(b);
    p/=2;
  }
  return ans;
}
FILE*fin,*fout;
void solve(){
  int x,y,z,a,b,c,n;
  fscanf(fin,"%d%d%d%d%d%d%d",&x,&y,&z,&a,&b,&c,&n);
  Matrix f(3,3,0);
  f.mat[1][0]=f.mat[2][1]=1;
  f.mat[0][2]=c;
  f.mat[1][2]=b;
  f.mat[2][2]=a;
  for(int i=0;i<f.n;i++){
    for(int j=0;j<f.m;j++)
      cerr<<f.mat[i][j]<<" ";
    cerr<<"\n";
  }
  cerr<<"\n\n";
  f=lgcput(f,n-2);
  for(int i=0;i<f.n;i++){
    for(int j=0;j<f.m;j++)
      cerr<<f.mat[i][j]<<" ";
    cerr<<"\n";
  }
  cerr<<"\n\n";
  Matrix ans(1,3,0);
  ans.mat[0][0]=x;
  ans.mat[0][1]=y;
  ans.mat[0][2]=z;
  ans=ans.mult(f);
  fprintf(fout,"%d\n",ans.mat[0][2]);
}
int main()
{

  fin=fopen("iepuri.in","r");
  fout=fopen("iepuri.out","w");
  int n;
  fscanf(fin,"%d",&n);
  while(n--)
    solve();
  return 0;
}