#include <stdio.h>
using namespace std;

#define MOD 666013

long long m[4][4], I[4][2], copie_m[4][4], c[4][4];
int baza[1001];
long long A, B,C, n, test, aux;
long long i, j, k, p;
int z, l;
int lg;

void afisare ()
{
    for (i=1; i<=3; ++i)
    {
        for (j=1; j<=3; ++j)
            printf ("%d ", m[i][j]);
        printf ("\n");
    }
    printf ("\n\n\n");
}

void inmultire (long long m[4][4], long long b[4][4])
{
    for (i=1; i<=3; ++i)
        for (j=1; j<=3; ++j)
            for (k=1; k<=3; ++k)
                c[i][k] += (m[i][j] * b[j][k]) % MOD;

    for (i=1; i<=3; ++i)
        for (j=1; j<=3; ++j)
        {
            m[i][j] = c[i][j];
            c[i][j] = 0;
        }
}

void inmultire_i (long long t[4][4], long long b[4][2])
{
    for (i=1; i<=3; ++i)
        for (j=1; j<=3; ++j)
            for (k=1; k<=1; ++k)
                c[i][k] += (t[i][j] * b[j][k]) % MOD;
    for (i=1; i<=3; ++i)
        for (j=1; j<=1; ++j)
        {
            b[i][j] = c[i][j];
            c[i][j] = 0;
        }
}

int main ()
{
    FILE *f = fopen ("iepuri.in","r");
    FILE *g = fopen ("iepuri.out","w");
    fscanf (f,"%lld", &test);

    for (z=1; z<=test; ++z)
    {
        fscanf (f,"%lld %lld %lld", &I[1][1], &I[2][1], &I[3][1]);
        fscanf (f,"%lld %lld %lld", &copie_m[3][3], &copie_m[3][2], &copie_m[3][1]);
        copie_m[1][2] = copie_m[2][3] = 1;
        m[1][1] = m[2][2] = m[3][3] = 1;
        fscanf (f,"%lld", &n);
        aux = n;
        lg = 0;
        while (aux)
        {
            lg ++;
            baza[lg] = aux % 2;
            aux /= 2;
        }
        for (p=lg; p>=1; --p)
        {
            inmultire (m, m);
            if (baza[p])
                inmultire (m, copie_m);
        }
        //afisare();
        inmultire_i(m, I);
        /*printf ("%d %d %d", I[1][1], I[2][1], I[3][1]);
        printf ("\n\n\n");*/
        fprintf (g,"%lld\n", I[1][1] % MOD);
        for (i=1; i<=3; ++i)
            for (j=1; j<=3; ++j)
                m[i][j] = 0;
    }


    fclose(g);
    fclose(f);
    return 0;
}