#include <cstdio>

using namespace std;

int main()
{
    long long a[4][4],v[4],v2[4],a2[4][4],n,t,i,j,k,l,m;
    for (i=0;i<4;++i)
    {
        v[i]=0;
        v2[i]=0;
        for (j=0;j<4;++j)
        {
            a[i][j]=0;
            a2[i][j]=0;
        }
    }
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    scanf("%lld\n",&t);
    for (m=1;m<=t;++m)
    {
        for (i=1;i<=3;++i)
            for (j=1;j<=3;++j)
                a[i][j]=0;
        scanf("%lld %lld %lld %lld %lld %lld %lld\n",&v[1],&v[2],&v[3],&a[3][3],&a[2][3],&a[1][3],&n);
        a[2][1]=1;a[3][2]=1;
        n-=2;
        for (l=1;l<=n;l<<=1)
        {
            if (l&n)
            {
                for (i=1;i<=3;++i)
                    for (j=1;j<=3;++j)
                        v2[i]+=v[j]*a[j][i];
                for (i=1;i<=3;++i)
                    v[i]=v2[i]%666013;
                for (i=1;i<=3;++i)
                    v2[i]=0;
            }
            for (i=1;i<=3;++i)
                for (j=1;j<=3;++j)
                    for (k=1;k<=3;++k)
                        a2[i][j]+=a[i][k]*a[k][j];
            for (i=1;i<=3;++i)
                for (j=1;j<=3;++j)
                {
                    a[i][j]=a2[i][j]%666013;
                    a2[i][j]=0;
                }
        }
        printf("%lld\n",v[3]);
    }
    return 0;
}