#include<stdio.h>


using namespace std;


const int MOD=666013;
const int MAX=5;
int m,p,a[MAX][MAX],in[MAX][MAX],d[MAX][MAX],c[MAX][MAX],i;

void inmultire(int a[][MAX],int b[][MAX],int c[][MAX],int m,int p,int q)
{
    int tmp[MAX][MAX];

    int s1,k,j;
    for (i=1;i<=m;i++)
        {
            for (j=1;j<=q;j++)
                {
                    s1=0;

                    for (k=1;k<=p;k++)
                        s1=(s1+(1LL*a[i][k]*b[k][j])%MOD)%MOD;
                    tmp[i][j]=s1;
                }
        }


    for (i=1;i<=m;i++)
        for (j=1;j<=q;j++)
            c[i][j]=tmp[i][j];
}

void putere (int a[][MAX],int p,int m,int put)
{
    int j;
    if (put==0)
    {
        for (i=1;i<=p;i++)
            for (j=1;j<=m;j++)
                a[i][j]=in[i][j];
    }
    else
        if (put%2==0)
        {
            inmultire (a,a,a,3,3,3);
            putere (a,3,3,put/2);
        }
        else
        {
            int rez[MAX][MAX];
              for (i=1;i<=p;i++)
                 for (j=1;j<=m;j++)
                    rez[i][j]=a[i][j];
              putere (a,3,3,put-1);
              inmultire (a,rez,a,3,3,3);
        }

}

int main()
{
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);

    int i,T,x,y,z,A,B,C,n;

    in[1][1]=1;
    in[2][2]=1;
    in[3][3]=1;

    scanf("%d",&T);
    for (i=1;i<=T;i++)
    {
        scanf("%d%d%d%d%d%d%d",&x,&y,&z,&A,&B,&C,&n);
        d[1][1]=x;d[1][2]=y;d[1][3]=z;

        a[3][1]=a[1][1]=a[1][2]=a[2][2]=0;
        a[2][1]=1;a[3][2]=1;a[1][3]=C;a[2][3]=B;a[3][3]=A;
        putere(a,3,3,n-2);
        inmultire(d,a,c,1,3,3);

        printf ("%d\n",c[1][3]);
    }

    return 0;
}