#include <fstream>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <climits>
#include <cstring>
using namespace std;
#define ll long long
#define KMAX 3

const int mod = 666013;
ll x, y, z, a, b, c, i, t, k, j;
ll n;

fstream f("iepuri.in");
ofstream g("iepuri.out");

void multiply_matrix(ll A[KMAX][KMAX], ll B[KMAX][KMAX], ll C[KMAX][KMAX]) {
    ll tmp[KMAX][KMAX];

    for (ll i = 0; i < KMAX; ++i) {
        for (ll j = 0; j < KMAX; ++j) {
            long long sum = 0;

            for (k = 0; k < KMAX; ++k) {
                sum = (1LL * sum % mod + 1LL * A[i][k] * B[k][j] % mod) % mod;
            }

            tmp[i][j] = sum;
        }
    }
    for(i = 0; i < KMAX; i++) {
      for(j = 0; j < KMAX; j++) {
        C[i][j] = tmp[i][j];
      }
    }
    //memcpy(C, tmp, sizeof(tmp));
}

void power_matrix(ll p) {

  ll C[KMAX][KMAX] = { {0, 0, c},
                       {1, 0, b},
                       {0, 1, a}};
  ll R[KMAX][KMAX];
  for (ll i = 0; i < KMAX; ++i) {
      for (ll j = 0; j < KMAX; ++j) {
          R[i][j] = 0;
      }
  }

    ll tmp[KMAX][KMAX];
    for (ll i = 0; i < KMAX; ++i) {
        for (ll j = 0; j < KMAX; ++j) {
            tmp[i][j] = (i == j) ? 1 : 0;
        }
    }

    while (p != 1) {
        if  (p % 2 == 0) {
            multiply_matrix(C, C, C);
            p /= 2;
        } else {
            multiply_matrix(tmp, C, tmp);
            --p;
        }
    }

    multiply_matrix(C, tmp, R);

      ll sol = 1LL * z * R[2][2] % mod + 1LL * y * R[1][2] % mod + 1LL * x * R[0][2] % mod;

      g << sol % mod << "\n";
}

void rez(ll n) {
  //if(n == 3) g << (a * z % mod + b * y % mod + c * x % mod) % mod << endl;

  /*ll C[KMAX][KMAX] = { {0, 0, c},
                       {1, 0, b},
                       {0, 1, a}};
  ll R[KMAX][KMAX];
  for(i = 0; i < KMAX; i++) {
    for(j = 0; j < KMAX; j++)
      R[i][j] = 0;
  }*/
  power_matrix(n - 2);
/*
  ll sol = 1LL * z * R[2][2] % mod + 1LL * y * R[1][2] % mod + 1LL * x * R[0][2] % mod;

  g << sol % mod << "\n";*/
}

int main() {

  f >> t;
  while(t--) {
    f >> x >> y >> z >> a >> b >> c >> n;
    rez(n);
    //cout << x << y << z << a << b << c << n << endl;
  }
  return 0;
}