#include<stdio.h>
#define dmax 4
#define modulo 666013
long long M[dmax][dmax]={0,0,0,0,
              0,0,0,0,
              0,1,0,0,
              0,0,1,0,
            };
long long rez[dmax][dmax], A[dmax][dmax], C[dmax][dmax], i, j, k, t, ii, x, y, z, a, b, c, n, jj;


void inmultire(long long a[dmax][dmax],long long b[dmax][dmax],long long n,long long p,long long m)
{
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
        {
            C[i][j]=0;
            for  (k=1;k<=p;k++)
                C[i][j]=(C[i][j]+a[i][k]*b[k][j])%modulo;
        }
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            a[i][j]=C[i][j];
}

void putere(long p)
{
    if (p==0)
    {
        for (i=1;i<=3;i++)
            for (j=1;j<=3;j++)
                rez[i][j]=0;
        rez[1][1]=rez[2][2]=rez[3][3]=1;
    }
    else
        if (p%2==0)
        {
            putere(p/2);
            inmultire(rez,rez,3,3,3);
        }
        else
        {
            putere(p-1);
            inmultire(rez,M,3,3,3);
        }
}

int main()
{
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    scanf("%ld",&t);
    for (ii=1;ii<=t;ii++)
    {
        scanf("%ld %ld %ld %ld %ld %ld %ld",&x,&y,&z,&a,&b,&c,&n);
        M[1][3]=c; M[2][3]=b; M[3][3]=a;
        putere(n-2);
        A[1][1]=x;  A[1][2]=y;  A[1][3]=z;
      /*  for (jj=3;jj<=n;jj++)
            inmultire(A,M,1,3,3);*/
        inmultire(A,rez,1,3,3);
        printf("%ld\n",A[1][3]);
    }
    return 0;
}