#include <fstream>
#define  MOD 666013

using namespace std;

ifstream cin ("iepuri.in");
ofstream cout ("iepuri.out");

struct matrice {
  int n, m, mat[4][4];
};

matrice multiply(matrice& A, matrice& B) {
  int i, j, l, na, ma, nb, mb;
  matrice sol;

  na = A.n; ma = A.m;
  nb = A.n; mb = B.m;

  for (i = 0; i < na; i++)
    for (j = 0; j < mb; j++)
      sol.mat[i][j] = 0;

  for (i = 0; i < na; i++)
    for (j = 0; j < mb; j++)
      for (l = 0; l < ma; l++)
        sol.mat[i][j] = (sol .mat[i][j] + (((long long)A.mat[i][l] * B.mat[l][j]) % MOD)) % MOD;


  sol.n = na; sol.m = mb;

  return sol;
}

matrice lgput(matrice A, int exp) {
  matrice sol;

  if (exp == 1)
    return A;

  exp -= 2;
  sol = multiply(A, A);

  while (exp > 0) {
    if (exp % 2 == 1)
      sol = multiply(sol, A);
    A = multiply(A, A);
    exp /= 2;
  }

  sol.n = A.n; sol.m = A.m;
  return sol;
}

int main() {
    int t, x, y, z, a, b, c, n;
    matrice A, B;
    cin >> t;

    B.mat[0][0] = B.mat[0][1] = B.mat[1][1] = B.mat[2][0] = 0;
    B.mat[1][0] = B.mat[2][1] = 1;

    while (t--) {
      cin >> x >> y >> z >> a >> b >> c >> n;
      B.mat[0][2] = c; B.mat[1][2] = b; B.mat[2][2] = a;
      A.mat[0][0] = x; A.mat[0][1] = y; A.mat[0][2] = z;
      A.n = 1; A.m = 3;
      B.n = B.m = 3;

      matrice IMI_BAG_PULA1 = lgput(B, n - 2);
      matrice IMI_BAG_PULA2 = multiply(A, IMI_BAG_PULA1);
      cout << IMI_BAG_PULA2.mat[0][2] << "\n";
    }
    return 0;
}