#include <cstdio>
using namespace std;

typedef long long i64;

const int MOD = 666013;

i64 M[3][3] = {{0, 0, 0},
               {1, 0, 0},
               {0, 1, 0}};

i64 I[3][3] = {{1, 0, 0},
               {0, 1, 0},
               {0, 0, 1}};

void multiply(i64 A[][3], i64 B[][3], i64 C[][3]) {
    int i, j, k;

    for (i = 0; i < 3; ++i) {
        for (j = 0; j < 3; ++j) {
            A[i][j] = 0;
            for (k = 0; k < 3; ++k)
                A[i][j] += B[i][k] * C[k][j];
            A[i][j] = A[i][j] % MOD;
        }
    }
}

void mcopy(i64 A[][3], i64 B[][3]) {
    int i, j;

    for (i = 0; i < 3; ++i)
        for (j = 0; j < 3; ++j)
            A[i][j] = B[i][j];
}

int main() {
    int x, y, z, n, k0, k1, i, O;
    i64 S[2][3][3], V[2][3][3];

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

    scanf("%d", &O);
    while (O--) {
        mcopy(V[0], M); mcopy(S[0], I);
        scanf("%d%d%d %lld%lld%lld %d", &x, &y, &z
                                      , &V[0][0][0]
                                      , &V[0][0][1]
                                      , &V[0][0][2]
                                      , &n);

        n -= 2;  k0 = k1 = 0;
        for (i = 1; i <= n; i <<= 1) {
            if (n & i) {
                multiply(S[1-k0], S[k0], V[k1]);
                k0 = 1-k0;
            }
            multiply(V[1-k1], V[k1], V[k1]);
            k1 = 1-k1;
        }

        printf("%lld\n", (z*S[k0][0][0] + y*S[k0][0][1] + x*S[k0][0][2])%MOD);
    }

    return 0;
}