#include<cstdio>
#define mod 666013
long long rez[4][4],a[4][4],ca[4][4];
int main ()
{freopen ("iepuri.in","r",stdin);
freopen ("iepuri.out","w",stdout);
long long n,i,j,k,x,y,z,A,B,C,t;
scanf("%lld",&t);
for(k=1;k<=t;k++)
    {scanf("%lld%lld%lld%lld%lld%lld%lld",&x,&y,&z,&A,&B,&C,&n);
    rez[1][1]=1;
    rez[2][2]=1;
    rez[3][3]=1;
    rez[1][2]=rez[1][3]=rez[2][1]=rez[2][3]=rez[3][1]=rez[3][2]=0;
    a[1][3]=C;
    a[2][3]=B;
    a[3][3]=A;
    a[2][2]=a[3][1]=1;
    a[1][1]=a[1][2]=a[2][1]=a[3][2]=0;
    n-=2;
    while(n)
        {if(n%2==1)
            {n--;
            for(i=1;i<=3;i++)
                for(j=1;j<=3;j++)
                    ca[i][j]=rez[i][j];
            rez[1][1]=((ca[1][1]*a[1][1])%mod+(ca[1][2]*a[2][1])%mod+(ca[1][3]*a[3][1])%mod)%mod;
            rez[1][2]=((ca[1][1]*a[1][2])%mod+(ca[1][2]*a[2][2])%mod+(ca[1][3]*a[3][2])%mod)%mod;
            rez[1][3]=((ca[1][1]*a[1][3])%mod+(ca[1][2]*a[2][3])%mod+(ca[1][3]*a[3][3])%mod)%mod;
            rez[2][1]=((ca[2][1]*a[1][1])%mod+(ca[2][2]*a[2][1])%mod+(ca[2][3]*a[3][1])%mod)%mod;
            rez[2][2]=((ca[2][1]*a[1][2])%mod+(ca[2][2]*a[2][2])%mod+(ca[2][3]*a[3][2])%mod)%mod;
            rez[2][3]=((ca[2][1]*a[1][3])%mod+(ca[2][2]*a[2][3])%mod+(ca[2][3]*a[3][3])%mod)%mod;
            rez[3][1]=((ca[3][1]*a[1][1])%mod+(ca[3][2]*a[2][1])%mod+(ca[3][3]*a[3][1])%mod)%mod;
            rez[3][2]=((ca[3][1]*a[1][2])%mod+(ca[3][2]*a[2][2])%mod+(ca[3][3]*a[3][2])%mod)%mod;
            rez[3][3]=((ca[3][1]*a[1][3])%mod+(ca[3][2]*a[2][3])%mod+(ca[3][3]*a[3][3])%mod)%mod;
            }
        else
            {n/=2;
            for(i=1;i<=3;i++)
                for(j=1;j<=3;j++)
                    ca[i][j]=a[i][j];
            a[1][1]=((ca[1][1]*ca[1][1])%mod+(ca[1][2]*ca[2][1])%mod+(ca[1][3]*ca[3][1])%mod)%mod;
            a[1][2]=((ca[1][1]*ca[1][2])%mod+(ca[1][2]*ca[2][2])%mod+(ca[1][3]*ca[3][2])%mod)%mod;
            a[1][3]=((ca[1][1]*ca[1][3])%mod+(ca[1][2]*ca[2][3])%mod+(ca[1][3]*ca[3][3])%mod)%mod;
            a[2][1]=((ca[2][1]*ca[1][1])%mod+(ca[2][2]*ca[2][1])%mod+(ca[2][3]*ca[3][1])%mod)%mod;
            a[2][2]=((ca[2][1]*ca[1][2])%mod+(ca[2][2]*ca[2][2])%mod+(ca[2][3]*ca[3][2])%mod)%mod;
            a[2][3]=((ca[2][1]*ca[1][3])%mod+(ca[2][2]*ca[2][3])%mod+(ca[2][3]*ca[3][3])%mod)%mod;
            a[3][1]=((ca[3][1]*ca[1][1])%mod+(ca[3][2]*ca[2][1])%mod+(ca[3][3]*ca[3][1])%mod)%mod;
            a[3][2]=((ca[3][1]*ca[1][2])%mod+(ca[3][2]*ca[2][2])%mod+(ca[3][3]*ca[3][2])%mod)%mod;
            a[3][3]=((ca[3][1]*ca[1][3])%mod+(ca[3][2]*ca[2][3])%mod+(ca[3][3]*ca[3][3])%mod)%mod;
            }
        }
    printf("%lld\n",(rez[1][3]*x+rez[2][3]*y+rez[3][3]*z)%mod);
    }
return 0;
}