#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

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

namespace {
  const int BUFFER_LIMIT = 100000;

  int char_counter = BUFFER_LIMIT - 1;
  char buffer[BUFFER_LIMIT];

  inline void check_buffer() {
    (++char_counter == BUFFER_LIMIT) ? (in.read(buffer, BUFFER_LIMIT), char_counter = 0) : (1);
  }

  void parse_integer(int &x){
    bool sign = 0;
    while (!((buffer[char_counter] >= '0' && buffer[char_counter] <= '9') || (buffer[char_counter] == '-' ))) check_buffer();

    if (buffer[char_counter] == '-') {
      check_buffer();
      sign = 1;
    }

    for (x = 0; (buffer[char_counter] >= '0' && buffer[char_counter] <= '9'); x *= 10, x += (buffer[char_counter] - '0'), check_buffer());
    if (sign) {
      x = -x;
    }
  }
}

const int MOD = 666013;

struct Matrix {
  int M[3][3];
  Matrix() {
    for (int i = 0; i < 3; i += 1) {
      for (int j = 0; j < 3; j += 1) {
        M[i][j] = 0;
      }
    }
  }
};

Matrix log_pow(Matrix &base, int exponent);
Matrix operator*(const Matrix &A, const Matrix &B);
int mod(long long x, int mod);
void print_matrix(const Matrix &M);

int main() {
  int t;
  check_buffer();
  parse_integer(t);

  int x, y, z, a, b, c, n;
  for (int i = 1; i <= t; ++i) {
    // fin >> x >> y >> z >> a >> b >> c >> n;
    parse_integer(x);
    parse_integer(y);
    parse_integer(z);
    parse_integer(a);
    parse_integer(b);
    parse_integer(c);
    parse_integer(n);

    Matrix M;
    M.M[0][1] = M.M[1][2] = 1;
    M.M[2][0] = c;
    M.M[2][1] = b;
    M.M[2][2] = a;

    M = log_pow(M, n - 3);

    out << mod(1LL * x * M.M[2][0] + 1LL * y * M.M[2][1] + 1LL * z * M.M[2][2], MOD) << '\n';
  }

  return 0;
}

Matrix log_pow(Matrix &base, int P) {
  Matrix result = base;
  for (int p = 1; p <= P; p *= 2) {
    if (p & P)
      result = result * base;
    base = base * base;
  }
  return result;
}

Matrix operator*(const Matrix &A, const Matrix &B) {
  Matrix result;
  for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 3; ++j) {
      for (int k = 0; k < 3; ++k) {
        result.M[i][j] += mod((1LL * A.M[i][k] * B.M[k][j]), MOD);
      }
    }
  }
  return result;
}

inline int mod(long long x, int m) {
  if (x < m) return x;
  if (x < 2 * m) return x - m;
  return x % m;
}