#include <stdio.h>

int A[4][4],M[12][4];
void init(int x,int y,int z,int a, int b, int c)
{
    M[1][1]=c;
    M[2][1]=b;
    M[3][1]=a;
    A[1][1]=x;
    A[1][2]=y;
    A[1][3]=z;
    A[2][1]=1;
    A[3][2]=1;
}
void inmultire()
{
    int i,j,R[4][4];

    for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
               R[i][j]=A[i][j]*M[j][1];
    int s=0;
    for(int k=1;k<=3;k++)
        {
            for(int l=1;l<=3;l++)
                s=s+R[k][l];
            M[k][1]=s;
            s=0;
        }
            }
int main()
{
    int nr,i,j,a,b,c,x,y,z,ziua;
    FILE*f;
    f=fopen("iepuri.in","r");
    g=fopen("iepuri.out","w");
    fscanf(f,"%d",&nr);
    for(i=1;i<=nr;i++)
    {
        fscanf(f,"%d%d%d",&x,&y,&z);
        fscanf(f,"%d%d%d",&a,&b,&c);
        init(x,y,z,a,b,c);
        fscanf(f,"%d",&ziua);
        for(j=3;j<=ziua;j++)
            inmultire();
        int val=M[1][1]%666013;
        fprintf(g,"%d ",val);
        fprintf(g,"\n");
    }



    return 0;
}