#include<stdio.h>
#define MOD 666013
int a[10][10];
int sol[10][10],N;
int X,Y,Z,A,B,C;
void inmu(int a[][10],int b[][10])
{

    int c[10][10];
    for(int i=1;i<=3;++i)
        for(int j=1;j<=3;++j)
            c[i][j]=0;
    for(int i=1;i<=3;++i)
        for(int j=1;j<=3;++j)
            for(int k=1;k<=3;++k)
            {
                c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j])%MOD;
            }
        for(int i=1;i<=3;++i)
            for(int j=1;j<=3;++j)
            {
                a[i][j]=c[i][j]%MOD;
            }
}
void afis(int q[][10])
{
   for(int i=1;i<=3;++i)
   {
       for(int j=1;j<=3;++j)
       {
           printf("%d ",q[i][j]);
       }
       printf("\n");
   }
   printf("\n");
}
void init()
{
    for(int i=1;i<=3;++i)
        {
            for(int j=1;j<=3;++j)
            {
            a[i][j]=0;
            sol[i][j]=0;
            }
        }
    a[1][1]=A;
    a[1][2]=B;
    a[1][3]=C;
    a[2][1]=1;
    a[3][2]=1;
    sol[1][1]=1;
    sol[2][2]=2;
    sol[3][3]=3;

    //afis(a);
}
void calc(int a[][10])
{
    printf("%d\n",(1LL*a[1][1]*Z+1LL*a[1][2]*Y+1LL*a[1][3]*X)%MOD);
}
void power()
{

    for(int i=0;(1<<i)<=N;++i)
    {
        if((1<<i)&N)
        {
        inmu(sol,a);
        }
        inmu(a,a);
    }
    calc(sol);
}

int main()
{
freopen("iepuri.in","r",stdin);
freopen("iepuri.out","w",stdout);
int T;
scanf("%d",&T);
while(T--)
{

    scanf("%d%d%d%d%d%d%d",&X,&Y,&Z,&A,&B,&C,&N);
    --N;--N;
     init();
    power();

}



}