#include <cstdio>
#define M 666013

long long A[4][4],rez[4][4],rez2[4][4],V[4],i,j,j2,k,put;
short int t;

void inmulteste(long long A[4][4], long long B[4][4])
{
    //inmulteste A cu B, memorand rezultatul in rez2
    int i,j,j2;

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

    for (i=1; i<=3; i++)
        for (j=1; j<=3; j++)
            for (j2=1; j2<=3; j2++) rez2[i][j]+=(A[i][j2]*B[j2][j])%M;
}

int main()
{
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    scanf("%d\n",&t);
    for (; t; t--)
    {
        for (i=1; i<=3; i++) scanf("%lld",&V[i]);
        for (i=3; i; i--) scanf("%lld",&A[3][i]);
        scanf("%lld",&put);
        A[1][2]=1; A[2][3]=1;

        //rez se initializeaza cu matricea unitate,
        //care e termen neutru in inmulturea matricelor
        for (i=1; i<=3; i++) rez[i][i]=1;
        //ridicarea la putere a matricei A in timp logaritmic,
        //rezultatul memorandu-se in rez
        for (k=1; k<=put; k<<=1)
        {
            if (k&put)
            {
                inmulteste(rez,A);
                for (i=1; i<=3; i++)
                    for (j=1; j<=3; j++) rez[i][j]=rez2[i][j];
            }
            inmulteste(A,A);
            for (i=1; i<=3; i++)
                for (j=1; j<=3; j++) A[i][j]=rez2[i][j];
        }
        k=0;
        for (i=1; i<=3; i++) k+=(rez[1][i]*V[i])%M;
        printf("%lld\n",k);
        for (i=1; i<=3; i++)
            for (j=1; j<=3; j++) rez[i][j]=0, A[i][j]=0;
    }

    return 0;
}