#include <fstream>

using namespace std;

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

const int MOD = 666013;

int M[4][4], I_3[4][4], Z[4][2];

int Q, N;

static inline void Reset ()
{
    for(int i = 1; i <= 3; ++i)
        for(int j = 1; j <= 3; ++j)
            M[i][j] = 0;

    M[1][2] = M[2][3] = 1;

    for(int i = 1; i <= 3; ++i)
        I_3[i][i] = 1;

    return;
}

static inline void Add (int &a, int b)
{
    a = (a + b) % MOD;

    return;
}

static inline void Multiply (int A[4][4], int B[4][4])
{
    int C[4][4];

    for(int i = 1; i <= 3; ++i)
        for(int j = 1; j <= 3; ++j)
        {
            C[i][j] = 0;

            for(int k = 1; k <= 3; ++k)
                Add(C[i][j], (1LL * A[i][k] * B[k][j]) % (1LL * MOD));
        }

    for(int i = 1; i <= 3; ++i)
        for(int j = 1; j <= 3; ++j)
            A[i][j] = C[i][j];

    return;
}

static inline void lgput (int M[4][4], int p)
{
    int ans[4][4], aux[4][4];

    for(int i = 1; i <= 3; ++i)
        for(int j = 1; j <= 3; ++j)
            ans[i][j] = I_3[i][j], aux[i][j] = M[i][j];

    for(int i = 0; (1LL << i) <= p; ++i)
    {
        if(p & (1LL << i))
            Multiply(ans, aux);

        Multiply(aux, aux);
    }

    for(int i = 1; i <= 3; ++i)
        for(int j = 1; j <= 3; ++j)
            M[i][j] = ans[i][j];

    return;
}

static inline void TestCase ()
{
    Reset();

    for(int i = 1; i <= 3; ++i)
        f >> Z[i][1];
    for(int j = 3; j >= 1; --j)
        f >> M[3][j];

    f >> N;
    lgput(M, N - 2);

    int ans = 0;
    for(int i = 1; i <= 3; ++i)
        Add(ans, (1LL * M[3][i] * Z[i][1]) % (1LL * MOD));
    g << ans << '\n';

    return;
}

int main()
{
    f.tie(nullptr);

    f >> Q;

    while(Q--)
        TestCase();

    return 0;
}