#include <cstdio>
const int modul = 666013;
int x, y, z, a, b, c, n;
long long p[4][4], sol[4][4], temp[4][4];

void produs(long long v1[4][4], long long v2[4][4], long long v3[4][4])
{
    int i, j, k;
    for (i=1; i<=3; ++i)
        for (j=1; j<=3; ++j)
            for (k=1; k<=3; ++k)
            {
                v3[i][j] += (v1[i][k] % modul) * (v2[k][j] % modul);
                v3[i][j] %= modul;
            }
}

void solve()
{
    int k;
    memset(p, 0, sizeof(p));
    memset(sol, 0, sizeof(sol));
    p[1][2] = p[2][3] = 1;
    p[3][1] = c;
    p[3][2] = b;
    p[3][3] = a;
    sol[1][1] = sol[2][2] = sol[3][3] = 1;
    for (k=0; k<32; k++)
    {
        if ((n >> k) & 1)
        {
            memset(temp, 0, sizeof(temp));
            produs(p, sol, temp);
            memcpy(sol, temp, sizeof(temp));
        }
        memset(temp, 0, sizeof(temp));
        produs(p, p, temp);
        memcpy(p, temp, sizeof(p));
    }
    int afis = (x * sol[1][1] + y * sol[1][2] + z * sol[1][3]) % modul;
    printf("%d\n", afis);
}



int main()
{
    freopen("iepuri.in", "r", stdin);
    freopen("iepuri.out", "w", stdout);
    int i, t;
    scanf("%d\n", &t);
    for (i=1; i<=t; ++i)
    {
        scanf("%d %d %d %d %d %d %d", &x, &y, &z, &a, &b, &c, &n);
        solve();
    }
    return 0;
}