#include <stdio.h>
#include <stdlib.h>
#define MOD 666013
int v[3],m[3][3],z[3][3],k[32][3][3],x,v2[3];
void prod()
{
    int i,j,ct;
    for(i=0; i<=2; i++)
        for(j=0; j<=2; j++)
            for(ct=0; ct<=2; ct++)
                z[i][j]+=((m[i][ct]%MOD)*(m[ct][j]%MOD)%MOD);
    for(i=0; i<=2; i++)
        for(j=0; j<=2; j++)
            m[i][j]=z[i][j];
}
void prod2()
{
    int i,j,ct,c;
    for(ct=1; ct<=x; ct++){
        for(i=0; i<=2; i++)
            for(j=0; j<=2; j++)
                for(c=0; c<=2; c++)
                    z[i][j]=(z[i][j]+((m[i][c]%MOD)*(k[x][c][j]%MOD)%MOD))%MOD;
        for(i=0; i<=2; i++)
            for(j=0; j<=2; j++)
                m[i][j]=z[i][j],z[i][j]=0;
    }
}
void retinere()
{
    x++;
    int i,j;
    for(i=0; i<=2; i++)
        for(j=0; j<=2; j++)
            k[x][i][j]=m[i][j];
}
void lgput(int n)
{
    if(n>1)
    {
        if(n%2==1)
            retinere();
        prod();
        lgput(n/2);
    }
}
int main()
{
    int q,i,t1,t2,t3,a,b,c,ct,j,n,d;
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    scanf("%d",&q);
    for(d=1; d<=q; d++)
    {
        scanf("%d%d%d%d%d%d%d",&t1,&t2,&t3,&c,&b,&a,&n);
        n-=2;
        v[0]=t1;
        v[1]=t2;
        v[2]=t3;
        m[0][2]=a;
        m[1][2]=b;
        m[2][2]=c;
        m[1][0]=m[2][1]=1;
        lgput(n);
        for(i=0; i<=2; i++)
            for(j=0; j<=2; j++)
                z[i][j]=0;
        prod2();
        for(j=0; j<=2; j++)
            for(i=0; i<=2; i++)
                v2[j]=(v2[j]+((v[i]%MOD)*(m[i][j]%MOD)%MOD))%MOD;
        for(i=0; i<=2; i++)
            for(j=0; j<=2; j++)
                m[i][j]=z[i][j]=0;
        x=0;
        printf("%d\n",v2[2]);
        v2[0]=v2[1]=v2[2]=0;
    }

    return 0;
}