#include<stdio.h>
#include<assert.h>
#define ORLY 666013

int t,m1[4][4],m2[4][4],m3[4][4],loli[4][2],sol[101],a[101],b[101],c[101],n[101],z[101],y[101],x[101];

void read()
{
    assert(freopen("iepuri.in","r",stdin)!=NULL);
    int i;
    assert(scanf("%d",&t)!=EOF);
    for(i=1;i<=t;++i)
        assert(scanf("%d%d%d%d%d%d%d",&x[i],&y[i],&z[i],&a[i],&b[i],&c[i],&n[i])!=EOF);
}

void exp(int k)
{
    if(k==1)
        return ;
    int i,j,l;
    if(k%2==0)
    {
        exp(k/2);
        for(i=1;i<=3;++i)
            for(j=1;j<=3;++j)
                for(l=1;l<=3;++l)
                {
                    m3[i][j]+=m2[i][l]*m2[l][j];
                    m3[i][j]%=ORLY;
                }
        for(i=1;i<=3;++i)
            for(j=1;j<=3;++j)
            {
                m2[i][j]=m3[i][j];
                m3[i][j]=0;
            }
        return;
    }
    exp(k/2);
    for(i=1;i<=3;++i)
        for(j=1;j<=3;++j)
            for(l=1;l<=3;++l)
            {
                m3[i][j]+=m2[i][l]*m2[l][j];
                m3[i][j]%=ORLY;
            }
    for(i=1;i<=3;++i)
        for(j=1;j<=3;++j)
        {
            m2[i][j]=0;
            for(l=1;l<=3;++l)
            {
                m2[i][j]+=m1[i][l]*m3[l][j];
                m2[i][j]%=ORLY;
            }
        }
    for(i=1;i<=3;++i)
        for(j=1;j<=3;++j)
            m3[i][j]=0;
}

void solve()
{
    int i,j,k;
    for(i=1;i<=t;++i)
    {
        loli[1][1]=x[i];
        loli[2][1]=y[i];
        loli[3][1]=z[i];
        m1[1][1]=0;m1[1][2]=1;m1[1][3]=0;
        m1[2][1]=0;m1[2][2]=0;m1[2][3]=1;
        m1[3][1]=c[i];m1[3][2]=b[i];m1[3][3]=a[i];
        for(j=1;j<=3;++j)
            for(k=1;k<=3;++k)
                m2[j][k]=m1[j][k];
        exp(n[i]-2);
        for(j=1;j<=3;++j)
            sol[i]+=m2[3][j]*loli[j][1];
        sol[i]%=ORLY;
    }
}

void write()
{
    assert(freopen("iepuri.out","w",stdout)!=NULL);
    int i;
    for(i=1;i<=t;++i)
        printf("%d\n",sol[i]);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}