#include <iostream>
#include <fstream>
#define ll long long
#define mod 666013
#define KMAX 3
using namespace std;

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

ll x,y,z,a,b,c,n,t, k, i, j;

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];
      }
    }
}

void rez(ll p)
{
    ll C[KMAX][KMAX] = { {0, 0, c},
                         {1, 0, b},
                         {0, 1, a}};

    ll tmp[KMAX][KMAX], R[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";
    //  g<<(1LL*R[0][2]*x%mod+1LL*R[1][2]*y%mod+1LL*R[2][2]*z%mod)%mod<<"\n";
}
int main()
{
    f>>t;
    while(t--)
    {
        f>>x>>y>>z>>a>>b>>c>>n;
        rez(n-2);
    }

    return 0;
}