#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

const int mod = 666013;

typedef long long Matrix[4][4];

int T, N, A, B, C, X, Y, Z;

inline void mult( Matrix A, Matrix B )
{
    Matrix aux;

    for ( int i = 1; i <= 3; ++i )
            for ( int j = 1; j <= 3; ++j )
                    aux[i][j] = 0;

    for ( int k = 1; k <= 3; ++k )
        for ( int i = 1; i <= 3; ++i )
            for ( int j = 1; j <= 3; ++j )
                aux[i][j] = ( aux[i][j] + A[i][k] * B[k][j] * 1LL ) % mod;

    for ( int i = 1; i <= 3; ++i )
            for ( int j = 1; j <= 3; ++j )
                    A[i][j] = aux[i][j];
}

int power()
{
    Matrix SOL, I;

    for ( int i = 1; i <= 3; ++i )
            for ( int j = 1; j <= 3; ++j )
                    SOL[i][j] = 0,
                    I[i][j] = 0;

    SOL[1][2] = SOL[2][3] = 1;
    SOL[3][1] = C; SOL[3][2] = B; SOL[3][3] = A;

    I[1][1] = 1;
    I[2][2] = 1;
    I[3][3] = 1;

    for ( int i = 0; ( 1 << i ) <= N; ++i )
    {
        if ( N & ( 1 << i ) )
        {
            mult( I, SOL );
        }

        mult( SOL, SOL );
    }

    return ( I[1][1] * X + I[1][2] * Y + I[1][3] * Z ) % mod;
}

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);

        printf("%d\n", power());
    }

    return 0;
}