#include <bits/stdc++.h>

using namespace std;

int T, X, Y, Z, A, B, C, N, M = 666013;

struct Matrix
{
    int a[3][3];

    void operator *= (Matrix &b)
    {
        int r[3][3]{};

        for(int i = 0; i < 3; i++)
        {
            for(int j = 0; j < 3; j++)
            {
                for(int k = 0; k < 3; k++)
                {
                    r[i][j] = (r[i][j] + 1LL * a[i][k] * b.a[k][j] % M) % M;
                }
            }
        }

        memcpy(a, r, 36);
    }

    void operator ^= (int p)
    {
        Matrix r = {1, 0, 0,
                    0, 1, 0,
                    0, 0, 1};

        while(p)
        {
            if(p & 1) r *= *this;

            *this *= *this; p >>= 1;
        }

        *this = r;
    }
};

int main()
{
    freopen("iepuri.in", "r", stdin);
    freopen("iepuri.out", "w", stdout);

    scanf("%d", &T);

    while(T--)
    {
        scanf("%d %d %d %d %d %d %d", &X, &Y, &Z, &A, &B, &C, &N);

        Matrix S = {X, Y, Z}, M1 = {0, 0, C,
                                    1, 0, B,
                                    0, 1, A};
        M1 ^= N; S *= M1;

        printf("%d\n", S.a[0][0]);
    }

    return 0;
}