#include<stdio.h>

#define  op 666013

long long p,solf;
long long i,j,n,k,b[4][4];
long long a[4],b2[4][4],ver,t;


void inmul()
{
    long long s,i,j,k,p,b1[4][4];
    for(i=0;i<=3;i++)
        for(j=0;j<=3;j++)
            b1[i][j]=0;
    for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
            {
            s=0;
            for(k=1;k<=3;k++)
                s=(s+b[i][k]*b[k][j])%op;
            b1[i][j]=s%op;
            }
    for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
            b[i][j]=b1[i][j];
}

void sol()
{
    long long i,j,k,p,b1[4][4];
    if (ver==0)
        {
        for(i=1;i<=3;i++)
            for(j=1;j<=3;j++)
                b2[i][j]=b[i][j];
         ver=1;
        }
        else
        {
        for(i=1;i<=3;i++)
            for(j=1;j<=3;j++)
                b1[i][j]=0;
        for(i=1;i<=3;i++)
            for(j=1;j<=3;j++)
                for(k=1;k<=3;k++)
                        b1[i][j]+=((long long)b2[i][k]*b[k][j])%op;
        for(i=1;i<=3;i++)
            for(j=1;j<=3;j++)
                {
                b2[i][j]=b1[i][j]%op;
                }

        }



}


int main()
{
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    scanf("%lld",&t);
    long long i1;
    for(i1=1;i1<=t;i1++)
        {
        solf=0;
        ver=0;
        for(i=1;i<=3;i++)
            for(j=1;j<=3;j++)
            {
                b2[i][j]=0;
                b[i][j]=0;
            }
        scanf("%lld %lld %lld %lld %lld %lld %lld",&a[1],&a[2],&a[3],&b[3][3],&b[3][2],&b[3][1],&n);
 /*       ver2[1]=a[1];
        ver2[2]=a[2];
        ver2[3]=a[3];
        for(i=4;i<=n+1;i++)
        {
             ver2[i]=(ver2[i-3]*b[3][1]+ver2[i-2]*b[3][2]+ver2[i-1]*b[3][3])%op;
        }  */
        b[1][2]=1;
        n=n-2;
        b[2][3]=1;
        for(p=1;p<=n;p<<=1)
            {
            if((n&p)!=0)sol();
            inmul();
            }
        for(j=1;j<=3;j++)
            solf=(solf+b2[3][j]*a[j])%op;
        printf("%d\n",solf%op);
   /*     printf("%d\n",ver2[n+3]); */
  /*      if (solf==ver2[n+3]) printf("1\n");
                else printf("0\n");
        memset(ver2,0,sizeof(ver2));*/
        memset(b,0,sizeof(b));
        memset(b2,0,sizeof(b2));
        memset(a,0,sizeof(a));
        }


    return 0;
}