#include <cstdio>
#include <algorithm>
#include <cstring>
#define mod 666013
#define maxN 3
int t, n, i, j, x, y, z, a, b, c, m[maxN][maxN], A[maxN][maxN];
void mul(int a[maxN][maxN], int b[maxN][maxN])
{
    int res[maxN][maxN], k;
    for (i = 0; i < maxN; ++ i)
        for (j = 0; j < maxN; ++ j)
        {
            res[i][j] = 0;
            for (k = 0; k < maxN; ++ k)
                res[i][j] = (res[i][j] + 1LL * a[i][k] * b[k][j]) % mod;
        }

    memcpy(a, res, sizeof(res));

}
void rsw()
{
    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);
        memset(m, 0, sizeof(m));
        memset(A, 0, sizeof(A));
        m[0][0] = x;
        m[0][1] = y;
        m[0][2] = z;
        A[0][2] = c;
        A[1][0] = 1;
        A[1][2] = b;
        A[2][1] = 1;
        A[2][2] = a;
        n -= 2;
        while (n)
        {
            if (n & 1)
                mul(m, A);
            mul(A, A);
           n >>= 1;
        }
        printf("%d\n", m[0][2]);
    }

}
int main()
{
    rsw();
    return 0;
}