#include <iostream>

#define NMAX 1000000000
#define MOD 666013

using namespace std;

struct Matrix {
  long long mat[4][4] ;
};

Matrix matbaz ;
Matrix matrez ;

Matrix inmultire (Matrix m1, Matrix m2 ) {
  Matrix mrez ;
  for (int i = 1 ; i <= 3 ; i++ ) {
    for (int j = 1 ; j <= 3 ; j++ ) {
      for (int k = 1 ; k <= 3 ; k++ ) {
        mrez.mat[i][j] += (m1.mat[i][k] + m2.mat[k][j]) % MOD ;
      }
    }
  }
  return mrez ;
}

int main()  {

  FILE *fin, *fout ;
  fin = fopen ("iepuri.in", "r" ) ;
  fout = fopen ("iepuri.out", "w" ) ;
  int n, x, y, z, t, a, b, c ;
  fscanf (fin, "%d", &t ) ;
  while (t > 0 ) {
    fscanf (fin, "%d%d%d%d%d%d%d", &x, &y, &z, &a, &b, &c, &n ) ;
    for (int i = 0 ; i <= 3 ; i++ )
      for (int j = 0 ; j <= 3 ; j++ )
        matrez.mat[i][j] = 0, matbaz.mat[i][j] = 0 ;
    matrez.mat[1][1] = matrez.mat[2][2] = matrez.mat[3][3] = 1 ;
    matbaz.mat[2][1] = matbaz.mat[3][2] = 1 ;
    n--;
    while (n > 0 ) {
      if (n % 2 == 0 ) {
        matbaz = inmultire (matbaz, matbaz ) ;
        n /= 2 ;
      }
      else {
        matrez = inmultire (matrez, matbaz ) ;
        n--;
      }
    }
    fprintf (fout, "%d ", matrez.mat[3][3]) ;
    t--;
  }
  return 0;
}