#include <iostream>
#include <cstring>
#include <fstream>

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[0][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));
}

void putere(int n)
{
    while(n > 0)
    {
        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;
}