#include <stdio.h>
#define m 666013
 
FILE *f=fopen("iepuri.in","r");
FILE *g=fopen("iepuri.out","w");
 
int main()
{
    int a,b,c,x,y,z,n,i,j,s,t,k,l;
    fscanf(f,"%d",&t);
    for(i=1;i<=t;i++)
    {
        int r[10003][3];
        fscanf(f,"%d%d%d%d%d%d%d",&x,&y,&z,&a,&b,&c,&n);
        r[1][1]=z;
        r[1][2]=y;
        r[1][3]=x;
        s=r[1][1]*a+r[1][2]*b+r[1][3]*c;
        l=s;
        for(j=2;j<=n-2;j++)
        {
            s=0;
            for(k=1;k<=3;k++)
            {
                if(k==1)
                {
                    r[j][k]=l;
                    s=s+r[j][k]*a;
                }
                else
                    if(k==2)
                    {
                        r[j][k]=r[j-1][k-1];
                        s=s+r[j][k]*b;
                    }
                    else
                    {
                        r[j][k]=r[j-1][k-1];
                        s=s+r[j][k]*c;
                    }
            l=s;
            }
        }
        fprintf(g,"%d\n",l%m);
    }
}