#include <cstdio>
#include <cstring>

using namespace std;

const int L = 4;
const int MOD = 666013;

int T , X , Y , Z , A , B , C , n;
int mat[3][L][L] , res[L][L] , aux[L][L] , crt[L][L];

void inmMat(int A[L][L] , int B[L][L] , int C[L][L] , int lim1 , int lim2)
{
    for (int i = 1; i <= 3; ++i)
        for (int j = 1; j <= 3; ++j)
            A[i][j] = 0;

    for (int i = 1; i <= lim1; ++i)
        for (int j = 1; j <= lim2; ++j)
            for (int it = 1; it <= 3; ++it)
                A[i][j] = (1LL * A[i][j] + 1LL * B[i][it] * C[it][j]) % MOD;
}

void lgPut(int P)
{
    memcpy(crt , mat[2] , sizeof(mat[2]));

    for (int i = 0; (1 << i) <= P; ++i)
    {
        if (((P & (1 << i)) >> i) == 1)
        {
            inmMat(aux , res , crt , 3 , 3);
            memcpy(res , aux , sizeof(aux));
        }

        inmMat(aux , crt , crt , 3 , 3);
        memcpy(crt , aux , sizeof(aux));
    }
    memcpy(mat[2] , res , sizeof(res));
}

void init()
{
    int aux[L][L]
    {
        0 , 0 , 0 , 0,
        0 , X , Y , Z,
    };
    memcpy(mat[1] , aux , sizeof(aux));

    int aux2[L][L]
    {
        0 , 0 , 0 , 0,
        0 , 0 , 0 , C,
        0 , 1 , 0 , B,
        0 , 0 , 1 , A,
    };
    memcpy(mat[2] , aux2 , sizeof(aux2));

    memset(res , 0 , sizeof(res));
    for (int i = 1; i <= 3; ++i)
        res[i][i] = 1;
}

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

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

        init();
        lgPut(n-2);
        inmMat(res , mat[1] , mat[2] , 1 , 3);
        printf("%d\n", res[1][3]);
    }

    return 0;
}