#include <cstdio>
using namespace std;

struct mat {
    int m[3][3];
};

mat mult(mat m1, mat m2) {
    int i, j, k;
    mat n;
    for(i = 0; i < 3; i++) {
        for(j = 0; j < 3; j++) {
            n.m[i][j] = 0;
            for(k = 0; k < 3; k++) {
                n.m[i][j] = (n.m[i][j] + ((long long)m1.m[i][k] * m2.m[k][j]) % 666013) % 666013;
            }
        }
    }
    return n;
}

mat rapexp(mat m, int e) {
    mat rez;
    if(e % 2) {
        rez = m;
        e--;
    } else {
        rez.m[0][0] = 1; rez.m[0][1] = 0; rez.m[0][2] = 0;
        rez.m[1][0] = 0; rez.m[1][1] = 1; rez.m[1][2] = 0;
        rez.m[2][0] = 0; rez.m[2][1] = 0; rez.m[2][2] = 1;
    }
    if(e != 0) {
        mat t = rapexp(m, e / 2);
        mat tt = mult(t, t);
        rez = mult(rez, tt);
    }
    return rez;
}

int T;
int A, B, C, X, Y, Z, N;

int main() {
    int i, j;
    freopen("iepuri.in", "r", stdin);
    freopen("iepuri.out", "w", stdout);
    scanf("%d", &T);
    while(T) {
        T--;
        scanf("%d %d %d %d %d %d %d", &X, &Y, &Z, &A, &B, &C, &N);
        mat m1, m2;
        m1.m[0][0] = Z; m1.m[0][1] = Y; m1.m[0][2] = X;
        m1.m[1][0] = Y; m1.m[1][1] = X; m1.m[1][2] = 0;
        m1.m[2][0] = X; m1.m[2][1] = 0; m1.m[2][2] = 0;

        m2.m[0][0] = A; m2.m[0][1] = 1; m2.m[0][2] = 0;
        m2.m[1][0] = B; m2.m[1][1] = 0; m2.m[1][2] = 1;
        m2.m[2][0] = C; m2.m[2][1] = 0; m2.m[2][2] = 0;

        m2 = rapexp(m2, N - 2);
        m1 = mult(m1, m2);
        printf("%d\n", m1.m[0][0]);
    }
    return 0;
}