#include <fstream>

using namespace std;

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

int n;
long long x, y, z, a, b, c;

const int MOD = 666013;

//inline void afis(long long m[3][3]) {
//    for (int i = 0; i < 3; i++) {
//        for (int j = 0; j < 3; j++) out << m[i][j] << ' ';
//        out << '\n';
//    }
//    out << '\n';
//}

inline void setm(long long m[3][3]) {
    m[0][1] = 1LL;
    m[1][2] = 1LL;
    m[2][0] = 1LL * c;
    m[2][1] = 1LL * b;
    m[2][2] = 1LL * a;
}

inline void setval(long long m[3][3], long long x) {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) m[i][j] = x;
    }
}

inline void setmatrix(long long temp[3][3], long long m[3][3]) {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) temp[i][j] = m[i][j];
    }
}

void mult(long long r[3][3], long long p[3][3], long long q[3][3]) {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                r[i][j] += p[i][k] * q[k][j];
                r[i][j] %= MOD;
            }
        }
    }
}

void putere(long long m[3][3], int pow) {
    if (pow == 1) return;

    long long temp[3][3], sec[3][3];
    setmatrix(temp, m);
    putere(m, pow >> 1);
    setmatrix(sec, m);
    //afis(m);
    setval(m, 0);

    mult(m, sec, sec);
    if (pow % 2 == 1) {
        setmatrix(sec, m);
        setval(m, 0);
        mult(m, sec, temp);
    }
    //afis(m);
}

void solve() {
    long long m[3][3];
    setval(m, 0);
    setm(m);
    putere(m, n);

    long long sum = 0, val[3] = {x, y, z};
    for (int i = 0; i < 3; i++) {
        sum += m[0][i] * val[i];
        sum %= MOD;
    }
    out << sum << '\n';
}

int main()
{
    int t;
    in >> t;
    for (int i = 0; i < t; i++) {
        in >> x >> y >> z >> a >> b >> c >> n;
        solve();
    }
    in.close();
    out.close();
}