#include <cstdio>
#include <cstring>
#define MOD 666013

using namespace std;

int q,t[4],a,b,c,n;
int M[5][5],R[5][5],aux[5][5],D[5][2];

void init()
{
    memset(M,0,sizeof(M));
    memset(R,0,sizeof(R));
    M[1][2]=1;
    M[2][3]=1;
    M[3][1]=c;
    M[3][2]=b;
    M[3][3]=a;

    D[1][1]=t[0];
    D[2][1]=t[1];
    D[3][1]=t[2];

    R[1][1]=1;
    R[2][2]=1;
    R[3][3]=1;
}

void inm(int A[5][5],int B[5][5],int C[5][5],int k1,int k2)
{
    for(int i=1; i<=3; ++i)
        for(int j=1; j<=3; ++j)
            C[i][j]=0;

    for(int i=1; i<=k1; ++i)
        for(int j=1; j<=k2; ++j)
            for(int k=1; k<=3; ++k)
            {
                C[i][j]+=(1LL*A[i][k]*B[k][j])%MOD;
                if(C[i][j]>=MOD)
                    C[i][j]-=MOD;
            }
}

void putere(int n)
{
    int bit;
    for(bit=0; bit<=30; ++bit)
    {
        if((n>>bit)&1)
        {
            inm(M,R,aux,3,3);
            memcpy(R,aux,sizeof(aux));
        }
        inm(M,M,aux,3,3);
        memcpy(M,aux,sizeof(aux));
    }
}

int main()
{
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);

    scanf("%d",&q);
    while(q--)
    {
        scanf("%d%d%d%d%d%d%d",&t[0],&t[1],&t[2],&a,&b,&c,&n);

        init();

        if(n<=2)
            printf("%d\n",t[n]);
        else
        {
            putere(n-2);
            inm(R,D,aux,3,1);
        }
        printf("%d\n",aux[3][1]);
    }
    return 0;
}