#include <cstdio>
#include <cstring>
const int MOD = 666013;
int B[3][3] = {{0, 0, 9}, {1, 0, 9}, {0, 1, 9}}, A[3][3];
int P[3][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};

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

int putere(int n)
{
    while(n > 0)
    {
        while((n & 1) == 0)
        {
            mul(A, A);
            n >>= 1;
        }
        mul(P, A);
        n--;
    }
    return P[0][2];
}

int main()
{
    freopen("iepuri.in", "r", stdin);
    freopen("iepuri.out", "w", stdout);
    int T, N;
    scanf("%d", &T);
    while(T--)
    {
        memcpy(A, B, sizeof(B));
        scanf("%d%d%d%d%d%d%d", &P[0][0], &P[0][1], &P[0][2], &A[2][2], &A[1][2], &A[0][2], &N);
        printf("%d\n", putere(N - 2));
    }
    return 0;
}