#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int MX = 3, MOD = 666013;

struct Matrix {
  ll a[MX + 1][MX + 1];
  Matrix () {
    memset (a, 0, sizeof (a));
  }
  Matrix operator * (const Matrix &other) const {
    Matrix sol;
    int i, j, k;
    for (i = 1; i <= MX; i++)
      for (j = 1; j <= MX; j++)
        for (k = 1; k <= MX; k++)
          sol.a[i][j] = (sol.a[i][j] + a[i][k] * other.a[k][j]) % MOD;
    return sol;
  }

};

Matrix lgput (Matrix a, int b) {
  Matrix sol;
  sol = a;
  while (b) {
    if (b & 1)
      sol = sol * a;
    a = a * a;
    b /= 2;
  }
  return sol;
}

inline void solve () {
  int x, y, z, a, b, c, n;
  scanf ("%d%d%d%d%d%d%d", &x, &y, &z, &a, &b, &c, &n);
  Matrix m1, m2;
  m2.a[1][3] = c;
  m2.a[2][3] = b;
  m2.a[3][3] = a;
  m2.a[3][2] = 1;
  m2.a[2][1] = 1;
  m1.a[3][1] = x;
  m1.a[3][2] = y;
  m1.a[3][3] = z;
  m2 = lgput (m2, n - 3);
  m1 = m1 * m2;
  printf ("%lld\n", m1.a[3][3]);
}

int main() {
  int t;
  freopen ("iepuri.in", "r", stdin);
  freopen ("iepuri.out", "w", stdout);
  scanf ("%d", &t);
  while (t--)
    solve ();
  return 0;
}