#include <fstream>
#include <cstring>
using namespace std;
const int MOD = 666013;
int A[3][3], B[3][3] = {{0, 0, 9}, {1, 0, 9}, {0, 1, 9}};
int P[3][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
int N;
ifstream f("iepuri.in");
ofstream g("iepuri.out");
void mul(int A[][3], int B[][3]) { // A <-- A*B

    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));

}
void putere(int n) {
    while(n > 0) {
        while(n % 2 == 0) {
            mul(A, A);
            n /= 2;
        }
        mul(P, A);
        n--;
    }
}
int main() {
    int T;
    f >> T;
    while(T--) {
        memcpy(A, B, sizeof(B));
        f >> P[0][0] >> P[0][1] >> P[0][2] >> A[2][2] >> A[1][2] >> A[0][2] >> N;
        putere(N-2);
        g << P[0][2] << '\n';
    }
    return 0;

}