#include <cstdio>

const int MAX_LATURA = 3;
const int LIM = 666013;

class Matrice {
private:
  int n, m;
  int matr[MAX_LATURA][MAX_LATURA];
public:
  Matrice();
  void setSides(int, int);
  void setMatrix(int*, int);
  void setElement(int, int, int);
  int getElement(int, int);
  Matrice operator* (Matrice a) {
    Matrice rez;
    int l, c, h, p, q, r;
    p = n;
    q = m;
    r = a.m;
    for(l = 0; l < p; l++)
      for(c = 0; c < r; c++) {
        rez.matr[l][c] = 0;
        for(h = 0; h < q; h++)
          rez.matr[l][c] = (rez.matr[l][c] + (long long)matr[l][h] * a.matr[h][c] % LIM) % LIM;
      }
    rez.n = p;
    rez.m = r;
    return rez;
  }
};

Matrice::Matrice() {
  int l, c;
  n = m = 0;
  for(l = 0; l < MAX_LATURA; l++)
    for(c = 0; c < MAX_LATURA; c++)
      matr[l][c] = 0;
}

void Matrice::setSides(int lin, int col) {
  n = lin;
  m = col;
}

void Matrice::setMatrix(int *v, int size) {
  int l, c;
  for(l = 0; l < n; l++)
    for(c = 0; c < m; c++) {
      if(l * m + c < size)
        matr[l][c] = v[l * m + c];
    }
}

void Matrice::setElement(int l, int c, int x) {
  matr[l][c] = x;
}

int Matrice::getElement(int l, int c) {
  return matr[l][c];
}

Matrice myPow(Matrice baza, int exp, Matrice acum) {
  if(exp == 0)
    return acum;
  else if(exp % 2 == 0)
    return myPow(baza * baza, exp / 2, acum);
  else
    return myPow(baza * baza, exp / 2, acum * baza);
}

int main() {
  int t, i, x, y, z, a, b, c, n;
  Matrice rez, mod;
  FILE *fin = fopen("iepuri.in", "r");
  FILE *fout = fopen("iepuri.out", "w");
  fscanf(fin, "%d", &t);
  rez.setSides(1, 3);
  mod.setSides(3, 3);
  for(i = 0; i < t; i++) {
    fscanf(fin, "%d%d%d%d%d%d%d", &x, &y, &z, &a, &b, &c, &n);
    rez.setElement(0, 0, x);
    rez.setElement(0, 1, y);
    rez.setElement(0, 2, z);
    mod.setElement(1, 0, 1);
    mod.setElement(2, 1, 1);
    mod.setElement(0, 2, c);
    mod.setElement(1, 2, b);
    mod.setElement(2, 2, a);
    rez = rez * myPow(mod, n - 3, mod);
    fprintf(fout, "%d\n", rez.getElement(0, 2));
  }
  fclose(fin);
  fclose(fout);
  return 0;
}