#include <bits/stdc++.h>
using namespace std;

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

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

void mul(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)); /// A <- C
}

void putere(int n) {
    while(n) {
        if (n % 2 == 0) {
            mul(A,A);
            n /= 2;
        }
        else {
            mul(P,A);
            n--;
        }
    }
}

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