#include <iostream>
#include <fstream>

using namespace std;
ifstream in ("iepuri.in");
ofstream out ("iepuri.out");
int const nmax = 10;
int const modulo = 666013;
struct Matrix{
  int n , m;
  int v[5 + nmax][5 + nmax];
  void clearmat(){
    for(int i = 1 ; i <= n ;i++){
      for(int j = 1 ; j <= m ;j++){
        v[i][j] = 0;
      }
    }
  }
  Matrix operator * (Matrix const a) const{
    Matrix result;
    result.n = n;
    result.m = a.m;
    result.clearmat();
    for(int i = 1 ; i <= n ;i++){
      for(int j = 1 ; j <= a.m ;j++){
        for(int h = 1 ; h <= m ;h++){
          result.v[i][j] += ((1LL * v[i][h] * a.v[h][j]) % modulo);
          result.v[i][j] %= modulo;
        }
      }
    }
    return result;
  }
};
Matrix lgpow(Matrix a , int b){
  if(b == 0){
    Matrix neutral;
    neutral.n = neutral.m = a.m;
    for(int i = 1 ; i <= neutral.n ;i++){
      neutral.v[i][i] = 1;
    }
    return neutral;
  } else if(b == 1)
    return a;
  else{
    Matrix result = lgpow(a , b / 2);
    if(b % 2 == 0)
      return result * result;
    else
      return result * result * a;
  }
}
int main()
{
  int t;
  in>>t;
  for(int test = 1 ; test <= t ;test++){
    Matrix a , b;
    a.n = a.m = b.n = b.m = 3;
    a.clearmat();
    b.clearmat();
    in>>a.v[1][3]>>a.v[1][2]>>a.v[1][1];
    in>>b.v[1][1]>>b.v[2][1]>>b.v[3][1];
    b.v[1][2] = 1;
    b.v[2][3] = 1;
    int n;
    in>>n;
    Matrix result = a * lgpow(b , n - 2);
    out<<result.v[1][1]<<'\n';
  }
  return 0;
}