#include <cstdio>
using namespace std;
const int MOD = 666013;
struct Mat {
  long long m[4][4];
};
Mat inm(Mat a, Mat b) {
  Mat c;
  for(int i = 1; i <= 3; i++) {
    for(int j = 1; j <= 3; j++) {
      c.m[i][j] = 0;
      for(int k = 1; k <= 3; k++) {
        c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD;
      }
    }
  }
  return c;
}
Mat lg(Mat a, int n) {
  Mat b;
  for(int i = 1; i <= 3; i++) {
    for(int j = 1; j <= 3; j++) {
      b.m[i][j] = a.m[i][j];
    }
  }
  while(n) {
    if(n % 2 == 1) {
      b = inm(a, b);
    }
    a = inm(a, a);
    n /= 2;
  }
  return b;
}

int main() {
  int T;
  freopen("iepuri.in", "r", stdin);
  freopen("iepuri.out", "w", stdout);
  scanf("%d", &T);
  while(T > 0) {
    T--;
    int x, y, z, a, b, c, n;
    scanf("%d%d%d%d%d%d%d", &x, &y, &z, &a, &b, &c, &n);
    Mat m1, m2;
    m1.m[1][1] = m1.m[1][2] = m1.m[2][2] = m1.m[3][1] = 0;
    m1.m[2][1] = m1.m[3][2] = 1;
    m1.m[1][3] = c;
    m1.m[2][3] = b;
    m1.m[3][3] = a;
    m2.m[3][1] = x;
    m2.m[3][2] = y;
    m2.m[3][3] = z;
    m2.m[2][1] = m2.m[2][2] = m2.m[2][3] = m2.m[1][1] = m2.m[1][2] = m2.m[1][3] = 0;
    m1 = lg(m1, n - 3);
    m2 = inm(m2, m1);
    printf("%lld\n", m2.m[3][3]);
  }
  return 0;
}