#include <cstdio>
#include <cstring>
using namespace std;
FILE*si=fopen("iepuri.in","r");
FILE*so=fopen("iepuri.out","w");
int aux[5][5],sol[5][5],v[5][5];
const int MOD=666013;
int main()
{
    int q;
    //si>>q;
    fscanf(si,"%i",&q);
    int p,n,i,j,k;
    while(q--)
    {
        fscanf(si,"%i %i %i %i %i %i %i",&sol[1][1],&sol[1][2],&sol[1][3],&v[3][3],&v[2][3],&v[1][3],&n);
        v[2][1]=v[3][2]=1;
        n-=2;
        for(p=1;p<=n;p<<=1)
        {
            if(n&p)
            {

                memset(aux,0,sizeof(aux));
                for(i=1;i<4;++i)
                {
                    for(j=1;j<4;++j)
                    {
                        for(k=1;k<4;++k)
                        {
                            aux[i][k]=(aux[i][k]+1LL*sol[i][j]*v[j][k])%MOD;
                        }
                    }
                }


                memcpy(sol,aux,sizeof(aux));
            }

            memset(aux,0,sizeof(aux));
            for(i=1;i<4;++i)
            {
                for(j=1;j<4;++j)
                {
                    for(k=1;k<4;++k)
                    {
                        aux[i][k]=(aux[i][k]+1LL*v[i][j]*v[j][k])%MOD;
                    }
                }
            }


            memcpy(v,aux,sizeof(aux));
            //cout<<'\n';

        }
        fprintf(so,"%i\n",sol[1][3]);


        memset(v,0,sizeof(v));
        memset(sol,0,sizeof(sol));
    }
    return 0;
}