#include <cstdio>
#include <cstring>

#define Mod 666013
#define LL long long

using namespace std;

int N;
LL F[3], Z[3][3], S;

inline void Copy (LL A[3][3], LL B[3][3])
{
    for (int i=0; i<3; ++i)
    {
        for (int j=0; j<3; ++j)
        {
            A[i][j]=B[i][j];
        }
    }
}

inline void Multiply (LL A[3][3], LL B[3][3])
{
    LL C[3][3];
    memset (C, 0, sizeof (C));
    for (int i=0; i<3; ++i)
    {
        for (int j=0; j<3; ++j)
        {
            for (int k=0; k<3; ++k)
            {
                C[i][j]+=(A[i][k]*B[k][j]);
                C[i][j]%=Mod;
            }
        }
    }
    Copy (A, C);
}

inline void Pow (LL A[3][3], int P)
{
    LL B[3][3];
    memset (B, 0, sizeof (B));
    B[0][0]=B[1][1]=B[2][2]=1;
    while (P>0)
    {
        if (P%2==0)
        {
            Multiply (A, A);
            P/=2;
        }
        else
        {
            Multiply (B, A);
            --P;
        }
    }
    Copy (A, B);
}

void Solve ()
{
    Pow (Z, N-2);
    S=(F[0]*Z[0][2]+F[1]*Z[1][2]+F[2]*Z[2][2])%Mod;
}

void Read ()
{
    scanf ("%lld %lld %lld", &F[0], &F[1], &F[2]);
    memset (Z, 0, sizeof (Z));
    Z[1][0]=Z[2][1]=1;
    scanf ("%lld %lld %lld", &Z[2][2], &Z[1][2], &Z[0][2]);
    scanf ("%d", &N);
}

void Print ()
{
    printf ("%lld\n", S);
}

int main()
{
    freopen ("iepuri.in", "r", stdin);
    freopen ("iepuri.out", "w", stdout);
    int T;
    scanf ("%d", &T);
    for (; T>0; --T)
    {
        Read ();
        Solve ();
        Print ();
    }
    return 0;
}