#include<cstdio>

const int N = 4;
const int MOD = 666013;

int i0, i1, i2, a, b, c, n, m[N][N], rez[N][N], aux[N][N], m2[N][N];

void init() {
    m[1][1] = m[1][3] = m[2][1] = m[2][2] = 0;
    m[1][2] = m[2][3] = 1;
    m[3][1] = c;
    m[3][2] = b;
    m[3][3] = a;

    rez[1][1] = rez[2][2] = rez[3][3] = 1;
    rez[1][2] = rez[1][3] = rez[2][1] = rez[2][3] = rez[3][1] = rez[3][2] = 0;
}

void copiere(int A[N][N], int aux[N][N]) {
    for (int i = 0; i < 4; ++i)
        for (int j = 0; j < 4; ++j)
            A[i][j] = aux[i][j];
}

void inmulteste(int A[N][N], int la, int ca, int B[N][N], int lb, int cb) {
    for (int i = 1; i <= la; ++i)
        for (int j = 1; j <= cb; ++j) {
            aux[i][j] = 0;

            for (int k = 1; k <= ca; ++k)
                aux[i][j] = ( aux[i][j] + (A[i][k] * B[k][j] % MOD) ) % MOD;
        }

    copiere(A, aux);
}

void ridica(int A[N][N], int put, int P[N][N]) {
    if (put == 0)
        return;

    while (put) {
        if (put & 1)
            inmulteste(P, 3, 3, A, 3, 3);

        inmulteste(A, 3, 3, A, 3, 3);

        put >>= 1;
    }
}

int main() {
    freopen("iepuri.in", "r", stdin);
    freopen("iepuri.out", "w", stdout);

    int t;
    scanf("%d", &t);

    for (; t > 0; --t) {
        scanf("%d%d%d%d%d%d%d", &i0, &i1, &i2, &a, &b, &c, &n);

        init();

        ridica(m, n, rez);

        m2[1][1] = i0;
        m2[2][1] = i1;
        m2[3][1] = i2;

        inmulteste(rez, 3, 3, m2, 3, 1);

        printf("%d\n", rez[1][1]);
    }

    return 0;
}