#include<stdio.h>
const int d=666013;
long long x0,x1,x2,n,a[4][4],a1,b1,c1,t;

int citire()
{
    long long i,j;
    scanf("%lld%lld%lld%lld%lld%lld%lld",&x0,&x1,&x2,&c1,&b1,&a1,&n);
    for(i=1;i<=3;++i)
        for(j=1;j<=3;++j)
            if(j==i+1)
                a[i][j]=1;
            else
                a[i][j]=0;
    a[3][1]=a1;a[3][2]=b1;a[3][3]=c1;

}

void ridput(long long r1[4][4], long long r2[4][4])
{
    int i,j,i1;
    long long a[4][4]={0},s;
    for(i=1;i<=3;++i)
        for(j=1;j<=3;++j)
        {
            s=0;
            for(i1=1;i1<=3;++i1)
            {
                s+=(r1[i][i1]*r2[i1][j])%d;
                s%=d;
            }
            a[i][j]=s;
        }
    for(i=1;i<=3;++i)
        for(j=1;j<=3;++j)
            r1[i][j]=a[i][j];
}



long long binar(int p)
{
    long long c[4][4]={{0,0,0,0},{0,1,0,0},{0,0,1,0},{0,0,0,1}},nr=0;
    while(p)
    {
        if(p%2)
            ridput(c,a);
        ridput(a,a);
        p>>=1;
    }
    nr=(x0*c[1][1]%d+x1*c[1][2]%d+x2*c[1][3]%d)%d;
    return nr;
}

int main()
{
    int i,t;
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    scanf("%d",&t);
    for(i=1;i<=t;++i)
    {
        citire();
        printf("%lld\n", binar(n));
    }
    return 0;
}