#include <iostream>
#include <stdio.h>

#define NMAX 1000000000
#define MOD 666013

using namespace std;

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

Matrix matbaz ;
Matrix matrez ;

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

int main()  {

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