#include <cstdio>

using namespace std;

int v[5][5], cv[5][5];

inline void inmult (int a[5][5], int b[5][5])
{
    int rez[5][5];
    for (int i = 1; i <= 4; ++i)
        for (int j = 1; j <= 4; ++j)
            rez[i][j] = 0;

    for (int i = 1; i <= 4; ++i)
        for (int j = 1; j <= 4; ++j)
            for (int h = 1; h <= 4; ++h)
            {
                long long x = 1LL * a[i][h] * b[h][j];
                x %= 666013LL;

                rez[i][j] += (int)x;
                rez[i][j] %= 666013;
            }

    for (int i = 1; i <= 4; ++i)
        for (int j = 1; j <= 4; ++j)
            a[i][j] = rez[i][j];
}

inline void put (int k)
{
    if (k < 2) return;
    put (k / 2);

    inmult (v, v);
    if (k & 1) inmult (v, cv);
}

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

    int t;
    scanf ("%d", &t);

    for (; t; --t)
    {
        int x, y, z, a, b, c, n;
        scanf ("%d %d %d %d %d %d %d", &x, &y, &z, &c, &b, &a, &n);

        v[2][1] = v[3][2] = v[4][3] = 1;
        v[2][4] = a;
        v[3][4] = b;
        v[4][4] = c;

        v[1][1] = v[1][2] = v[1][3] = v[2][2] = v[2][3] = v[3][1] = v[3][3] = v[4][1] = v[4][2] = v[1][4] = 0;

        for (int i = 1; i <= 4; ++i)
            for (int j = 1; j <= 4; ++j)
                cv[i][j] = v[i][j];

        put (n);

        int first[5] = {0, x, y, z, (x * a + y * b + z * c) % 666013}, sol = 0;

        for (int i = 1; i <= 4; ++i)
        {
            long long xx = 1LL * first[i] * v[i][1];
            xx %= 666013LL;

            sol += (int)xx;
            sol %= 666013;
        }

        printf ("%d\n", sol);
    }

    return 0;
}