#include <cstdio>
#include <cstring>
#define Mod 666013
using namespace std;

FILE *fin=freopen("iepuri.in","r",stdin);
FILE *fout=freopen("iepuri.out","w",stdout);

int M[3][3], Sol[3][3], Aux[3][3];
int t, a, b, c, x, y, z, n;

void Initialize()
{
    Sol[0][1] = Sol[0][2] = Sol[1][0] = Sol[1][2] = Sol[2][1] = Sol[2][0] = 0;
    Sol[0][0] = Sol[1][1] = Sol[2][2] = 1;
}

void Multiply_1()
{
    int i, j, l;
    for(i = 0; i < 3; ++i)
        for(j = 0; j < 3; ++j)
            Aux[i][j] = 0;

    for(i = 0; i < 3; ++i)
        for(j = 0; j < 3; ++j)
            for(l = 0; l < 3 ; ++l)
                Aux[i][j] = (1LL * Sol[i][l] * M[l][j] + Aux[i][j]) % Mod;

    for(i = 0; i < 3; ++i)
        for(j = 0; j < 3; ++j)
            Sol[i][j] = Aux[i][j];

}

void Multiply_2()
{
    int i, j, l;
    for(i = 0; i < 3; ++i)
        for(j = 0; j < 3; ++j)
            Aux[i][j] = 0;

    for(i = 0; i < 3; ++i)
        for(j = 0; j < 3; ++j)
            for(l = 0; l < 3 ; ++l)
                Aux[i][j] = (1LL * M[i][l] * M[l][j] + Aux[i][j]) % Mod;

    for(i = 0; i < 3; ++i)
        for(j = 0; j < 3; ++j)
            M[i][j] = Aux[i][j];
}

void Pow(int p)
{
    int i = 1;

    memset(M, 0, sizeof(M));
    M[1][0] = M[2][1] = 1;
    M[0][2] = c, M[1][2] = b, M[2][2] = a;

    for(; i <= p; i <<= 1)
    {
        if(i & p)
            Multiply_1();
        Multiply_2();
    }
    printf("%d\n", (1LL * Sol[0][2] * x + 1LL * Sol[1][2] * y + 1LL * Sol[2][2] * z) % Mod);
}

int main()
{

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

        Initialize();
        Pow(n - 2);
    }
}