#include <iostream>
#include <cstdio>

using namespace std;

const long long MOD = 666013;


struct matrix {
  long long val[3][3];

  matrix() {
    for(int i = 0; i < 3; i++)
      for(int j = 0; j < 3; j++)
        val[i][j] = 0;
  }

  void ide() {
    for(int i = 0; i < 3; i++)
      val[i][i] = 1;
  }

  void init(int x, int y, int z) {
    val[0][0] = x;
    val[0][1] = y;
    val[0][2] = z;
  }

  void mult(int a, int b, int c) {
    val[1][0] = 1;
    val[2][1] = 1;
    val[0][2] = c;
    val[1][2] = b;
    val[2][2] = a;
  }

  const matrix operator * (const matrix dr) const {
    matrix aux = matrix(); /// aux = (*this) * dr

    for(int i = 0; i < 3; i++)
      for(int j = 0; j < 3; j++)
        for(int k = 0; k < 3; k++)
          aux.val[i][j] = (aux.val[i][j] + this->val[i][k] * dr.val[k][j]) % MOD;

    return aux;
  }
};


matrix fast_pow(matrix a, int pow) {
  matrix r = matrix();
  r.ide();

  while(pow) {
    if(pow & 1)
      r = r * a;
    a = a * a;
    pow >>= 1;
  }

  return r;
}

int main() {
  freopen("iepuri.in", "r", stdin);
  freopen("iepuri.out", "w", stdout);
  int t, n, x, y, z, a, b, c;

  scanf("%d", &t);
  while(t--) {
    scanf("%d %d %d %d %d %d %d", &x, &y, &z, &a, &b, &c, &n);
    matrix ans = matrix();
    ans.init(x, y, z);

    if(n <= 2)
      printf("%lld\n", ans.val[0][n]);
    else {
      matrix mult = matrix();
      mult.mult(a, b, c);
      mult = fast_pow(mult, n - 2);

      ans = ans * mult;
      printf("%lld\n", ans.val[0][2]);
    }
  }

  return 0;
}