/*
        (0 1 0)   (D[i-2])   (D[i-1])
    M = (0 0 1) * (D[i-1]) = ( D[i] )
        (C B A)   ( D[i] )   (D[i+1])

    sau altfel:

        (A B C)   (D[i-1])   ( D[i] )
    M = (1 0 0) * (D[i-2]) = (D[i-1])
        (0 1 0)   (D[i-3])   (D[i-2])

    D[i] = A * D[i-1] + B * D[i-2] + C * D[i-3]


    (D[n-2])             (D[0])
    (D[n-1]) = M^(n-2) * (D[1])
    ( D[n] )             (D[2])
*/

#include <cstdio>

const int R = 666013;

int x,y,z,a,b,c,n;

int m[3][3];

/**
 * int m[3][3] = {{0, 1, 0},
 *                {0, 0, 1},
 *                {0, 0, 0}};
 */

void initializeaza_m()
{
    m[0][0] = 0;
    m[0][1] = 1;
    m[0][2] = 0;
    m[1][0] = 0;
    m[1][1] = 0;
    m[1][2] = 1;
}

void completeaza_m()
{
    m[2][0] = c;
    m[2][1] = b;
    m[2][2] = a;
}

void atrib_i3(int m[][3])
{
    for (int i = 0; i <= 2; ++i)
        for (int j = 0 ; j <= 2; ++j)
            m[i][j] = (i==j)?1:0;
}

void inmultire(int a[][3], int b[][3], int r[][3])
{
    for (int i = 0; i <= 2; ++i)
        for (int j = 0; j <= 2; ++j)
        {
            r[i][j] = 0;
            for (int k = 0; k <= 2; ++k)
                r[i][j] += ((long long)a[i][k] * b[k][j])%R;
            r[i][j] = r[i][j]%R;
        }
}

void putere(int m[][3], int n, int r[][3])
{
    int a[3][3];
    if (n == 0)
    {
        atrib_i3(r);
        return;
    }
    if (n % 2 == 0)
    {
        putere(m,n/2,a);
        inmultire(a,a,r);
    }
    else
    {
        putere(m,n-1,a);
        inmultire(a,m,r);
    }
}

void rezolva()
{
    int r[3][3];
    completeaza_m();
    putere(m,n-2,r);
    printf("%d\n",((long long)r[2][0] * x + (long long)r[2][1] * y + (long long)r[2][2] * z) % R);
}

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