#include <bits/stdc++.h>

using namespace std;

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

const int MOD = 666013;
int P[3][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}},
    B[3][3] = {{0, 0, 9}, {1, 0, 9}, {0, 1, 9}},
    A[3][3], T;

void inm(int A[][3], int B[][3]) {
    int C[3][3];

    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++) {
            long long x = 0;
            for(int k = 0; k < 3; k++)
                x += (long long) A[i][k] * B[k][j];
            C[i][j] = x % MOD;
        }
    memcpy(A, C, sizeof(C));
}

int lgPow(int p) {
    while(p > 0) {
        if(p & 1)
            inm(P, A);
        inm(A, A);
        p >>= 1;
    }
}

int main()
{
    in >> T;

    while(T--) {
        int n;
        memcpy(A, B, sizeof(B));
        in >> P[0][0] >> P[0][1] >> P[0][2] >> A[2][2] >> A[1][2] >> A[0][2] >> n;

        lgPow(n-2);
        out << P[0][2] << '\n';
    }
    return 0;
}