#include <stdio.h>
long long t[4][4],a1[4][4],v[4][4],arr[4],arr2[4];
long long a,b,c,x,y,z,n;
void inm()
{
    for(int i=1;i<=3;i++)
     {
             for(int j=1;j<=3;j++)
             {
                     t[i][j]=0;
                     for(int k=1;k<=3;k++)
                     {
                             t[i][j]+=(int)v[i][k]*v[k][j]%666013;
                     }
             }
     }
     for(int i=1;i<=3;i++)
     {
             for(int j=1;j<=3;j++) v[i][j]=t[i][j];
     }
}
int rid(int putere)
{
     if(putere!=1)
     {
                  rid(putere/2);
                  inm();
                  if(putere%2==1)
                  {
                                 for(int i=1;i<=3;i++)
                                 {
                                         for(int j=1;j<=3;j++)
                                         {
                                                 t[i][j]=0;
                                                 for(int k=1;k<=3;k++)
                                                 {
                                                         t[i][j]+=(int)v[i][k]*a1[k][j]%666013;
                                                 }
                                         }
                                 }
                                 for(int i=1;i<=3;i++)
                                 {
                                         for(int j=1;j<=3;j++) v[i][j]=t[i][j];
                                 }
                  }
     } 
}
int main()
{
    freopen ("iepuri.in","r",stdin);
    freopen ("iepuri.out","w",stdout);
    int timp;
    scanf("%d",&timp);
    for(int xy=1;xy<=timp;xy++)
    {
            scanf("%lld%lld%lld%lld%lld%lld%lld",&x,&y,&z,&a,&b,&c,&n);
            arr[1]=x;
            arr[2]=y;
            arr[3]=z;
            a1[1][1]=0;
            a1[2][1]=1;
            a1[3][1]=0;
            a1[1][2]=0;
            a1[2][2]=0;
            a1[3][2]=1;
            a1[1][3]=c;
            a1[2][3]=b;
            a1[3][3]=a;
            for(int i=1;i<=3;i++)
            {
                    arr2[i]=0;
                    for(int j=1;j<=3;j++) 
                    {
                            v[i][j]=a1[i][j];
                           // printf("%d ",v[i][j]);
                    }
                    //printf("\n");
            }
            //printf("\n");
            rid(n-2);
            /*for(int i=1;i<=3;i++)
            {
                    for(int j=1;j<=3;j++)
                    {
                     //       printf("%d ",t[i][j]);
                    }
                    //printf("\n");
            }*/
            for(int i=1;i<=3;i++)
            {
                    for(int j=1;j<=3;j++)
                    {
                            arr2[i]+=arr[j]*t[j][i];
                            arr2[i]%=666013;
                    }
            }
            printf("%d\n",arr2[3]);
    }
}