#include <stdio.h>

long long mod=666013;

int t;
long long zi1,zi2,zi3,zifin,m1[4][4],m2[4][4];

void mul1()
{
    long long c[4][4];
    int i,j,k;
    for(i=1;i<=3;++i)
        for(j=1;j<=3;++j)
            {
                c[i][j]=0;
                for(k=1;k<=3;++k)
                    c[i][j]=(long long)((long long)(c[i][j]%mod)+(long long)((long long)(m1[i][k]*m1[k][j])%mod))%mod;
            }
    for(i=1;i<=3;++i)
        for(j=1;j<=3;++j)
            m1[i][j]=c[i][j];
}

void mul2()
{
    long long c[4][4];
    int i,j,k;
    for(i=1;i<=3;++i)
        for(j=1;j<=3;++j)
            {
                c[i][j]=0;
                for(k=1;k<=3;++k)
					c[i][j]=(long long)((long long)(c[i][j]%mod)+(long long)((long long)(m2[i][k]*m1[k][j])%mod))%mod;
            }
    for(i=1;i<=3;++i)
        for(j=1;j<=3;++j)
            m2[i][j]=c[i][j];
}

int main()
{
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    int i,X,Y,Z,A,B,C,N,j,p,k;
    scanf("%d",&t);
    for(i=1;i<=t;++i)
        {
            scanf("%d%d%d%d%d%d%d",&X,&Y,&Z,&A,&B,&C,&N);
          /*  zi1=X;
            zi2=Y;
            zi3=Z;
            for(j=3;j<=N;++j)
                {
                    zifin=((zi3*A)%mod+(zi2*B)%mod+(zi1*C)%mod)%mod;
                    zi1=zi2;
                    zi2=zi3;
                    zi3=zifin;
                }*/
            m1[1][1]=X;
            m1[1][2]=Y;
			m1[1][3]=Z;
			m1[2][1]=1;
			m1[2][2]=0;
			m1[2][3]=0;
			m1[3][2]=1;
			m1[3][1]=0;
			m1[3][3]=0;
			for(k=1;k<=3;++k)
                for(j=1;j<=3;++j)
                    m2[k][j]=(k==j)?1:0;
            p=N-2;
            while(p)
            {
                if(p%2==1)
                     mul2();
                mul1();
                p/=2;
            }
            long long rez=(long long)(((long long)(m2[1][1]*A)%mod)+(long long)((long long)(m2[1][2]*B)%mod)+(long long)((long long)(m2[1][3]*C)%mod)%mod);
            printf("%lld\n",rez);
        }

    return 0;
}