#include <cstdio>
#include <fstream>
#include <iostream>
 
using namespace std;
 
ifstream in("iepuri.in");
ofstream out("iepuri.out");
 
int N = 666013;
 
typedef struct m3 {
  long long a11;
  long long a12;
  long long a13;
  long long a21;
  long long a22;
  long long a23;
  long long a31;
  long long a32;
  long long a33;
} m3;
 
void printm(m3 initial) {
  cout << initial.a11 << " " << initial.a12 << " " << initial.a13 << "\n";
  cout << initial.a21 << " " << initial.a22 << " " << initial.a23 << "\n";
  cout << initial.a31 << " " << initial.a32 << " " << initial.a33 << "\n";
  cout << "**********************\n";
}
 
m3 mul_matrix(m3 x1, m3 x2) {
  m3 res;
  res.a11 = (x1.a11 * x2.a11 + x1.a12 * x2.a21 + x1.a13 * x2.a31) % N;
  res.a12 = (x1.a11 * x2.a12 + x1.a12 * x2.a22 + x1.a13 * x2.a32) % N;
  res.a13 = (x1.a11 * x2.a13 + x1.a12 * x2.a23 + x1.a13 * x2.a33) % N;
  res.a21 = (x1.a21 * x2.a11 + x1.a22 * x2.a21 + x1.a23 * x2.a31) % N;
  res.a22 = (x1.a21 * x2.a12 + x1.a22 * x2.a22 + x1.a23 * x2.a32) % N;
  res.a23 = (x1.a21 * x2.a13 + x1.a22 * x2.a23 + x1.a23 * x2.a33) % N;
  res.a31 = (x1.a31 * x2.a11 + x1.a32 * x2.a21 + x1.a33 * x2.a31) % N;
  res.a32 = (x1.a31 * x2.a12 + x1.a32 * x2.a22 + x1.a33 * x2.a32) % N;
  res.a33 = (x1.a31 * x2.a13 + x1.a32 * x2.a23 + x1.a33 * x2.a33) % N;
  return res;
}
 
m3 pow_matrix(m3 initial, int n) {
  if (n == 1) {
    return initial;
  }
  m3 res = pow_matrix(initial, n/2);
  res = mul_matrix(res, res);
  if (n % 2 == 0) {
    return res;
  } else {
    return mul_matrix(res, initial);
  }
}
 
int solve(int x, int y, int z, int a, int b, int c, int n) {
  if (n == 0) return x;
  if (n == 1) return y;
  if (n == 2) return z;
  //cout << x << " " << y << " " << z << " " << a << " " << b << " " << c << " " << n << " " <<"\n------------------\n";
  m3 initial;
  initial.a11 = a; initial.a12 = b; initial.a13 = c;
  initial.a21 = 1; initial.a22 = 0; initial.a23 = 0;
  initial.a31 = 0; initial.a32 = 1; initial.a33 = 0;
  //printm(initial);
  m3 result = pow_matrix(initial, n - 2);
  //printm(result);
  return (result.a11 * z + result.a12 * y + result.a13 * x) % N;
}
 
int main() {
  int total;
  in >> total;
  for (int i = 0; i < total; i++) {
    int x, y, z, a, b, c, n;
    in >> x >> y >> z >> a >> b >> c >> n;
    out << solve(x, y, z, a, b, c, n) << "\n";
  }
}