#include <bits/stdc++.h>

using namespace std;

ifstream F("iepuri.in");
ofstream G("iepuri.out");

int n, t, a, b, c, x, y, z;
const int N = 3;
const int MOD = 666013;

struct matrix {
  int m[N][N];
  matrix()
  {
     memset(m, 0, sizeof(m));
  }
  matrix operator * (matrix b)
  {
     matrix c = matrix();
     //matrix c;
     for (int i = 0; i < N; ++i)
       for (int j = 0; j < N; ++j)
         for (int k = 0; k < N; ++k)
           c.m[i][j] = (c.m[i][j] + 1LL * m[i][k] * b.m[k][j]) % MOD;
     return c;
  }
};

matrix I3, A, init, rez;

matrix put( matrix X , int p )
{
    if( !p ) return I3;
    if( p == 1 ) return X;
    matrix aux = put( X , p / 2 );
    aux = aux * aux;
    if( p % 2 ) aux = aux * X;
    return aux;
}

int main()
{
    F >> t;
    I3.m[ 0 ][ 0 ] = I3.m[ 1 ][ 1 ] = I3.m[ 2 ][ 2 ] = 1;
    A.m[ 1 ][ 0 ] = 1;
    A.m[ 2 ][ 1 ] = 1;
    while( t -- )
    {
        F >> x >> y >> z >> a >> b >> c >> n;
        init.m[ 0 ][ 0 ] = x;
        init.m[ 0 ][ 1 ] = y;
        init.m[ 0 ][ 2 ] = z;
        A.m[ 0 ][ 2 ] = c;
        A.m[ 1 ][ 2 ] = b;
        A.m[ 2 ][ 2 ] = a;
        rez = put( A , n - 2 );
        rez = init * rez;
        G << rez.m[ 0 ][ 2 ] << '\n';
    }
    return 0;
}