#include <iostream>
#include <fstream>
#define P(x, y) (1LL * x * y) % 666013
#define S(x, y) (x + y) % 666013

using namespace std;
int T, sol[4][4], Z[4][4], M[4][4], A[4][4], B[4][4];
void produs1()
{
     for(int i = 1; i <= 3; ++i)
      for(int j = 1; j <= 3; ++j)
         A[i][j] = B[i][j] = Z[i][j];
    for(int i = 1; i <= 3; ++i)
      for(int j = 1; j <= 3; ++j){
       Z[i][j] = 0;
       for(int k = 1; k <= 3; ++k)
          Z[i][j] = S(Z[i][j], P(A[i][k], B[k][j]));
      }

}
void produs2()
{
   for(int i = 1; i <= 3; ++i)
      for(int j = 1; j <= 3; ++j)
         A[i][j] = sol[i][j], B[i][j] = Z[i][j];
    for(int i = 1; i <= 3; ++i)
      for(int j = 1; j <= 3; ++j){
       sol[i][j] = 0;
       for(int k = 1; k <= 3; ++k)
          sol[i][j] = S(sol[i][j], P(A[i][k], B[k][j]));
      }
}
void solve(int n)
{
   for(int i = 1; i <= 3; ++i)
     for(int j = 1; j <= 3; ++j)
       if(i == j) sol[i][j] = 1;
         else sol[i][j] = 0;
   while(n){
      if(n % 2 == 0){
        produs1();
        n /= 2;
      }
      else {
        n--;
        produs2();
      }
   }
}
void write();
void read()
{
    ifstream fin("iepuri.in");
    ofstream fout("iepuri.out");
    fin >> T;
    int x, y, z, a, b, c, n;

    for(int i = 1; i <= T; ++i){
        Z[1][1] = Z[1][2] = Z[2][2] = Z[3][1] = 0;
        Z[2][1] = Z[3][2] = 1;
        fin >> x >> y >> z >> a >> b >> c >> n;
        Z[1][3] = c;
        Z[2][3] = b;
        Z[3][3] = a;
        M[1][1] = x;
        M[1][2] = y;
        M[1][3] = z;
        solve(n - 2);
        fout << S(S(P(sol[1][3], x), P(sol[2][3], y)), P(sol[3][3], z)) << '\n';
    }
}
void write()
{
    for(int i = 1; i <= 3; ++i){
      for(int j = 1; j <= 3; ++j)
            cout << sol[i][j] << ' ';
      cout << '\n';
   }
   cout << '\n';
}
int main()
{
    read();
    return 0;
}