#include<cstdio>
using namespace std;
int x,y,z,a,b,c,n,t,solf;
#define mod 666013
struct mat
{
    long long a11,a12,a13,a21,a22,a23,a31,a32,a33;
};
mat init;
mat lg_pow(int p)
{
    if(p<=1) return init;
    mat v=lg_pow(p/2);
    mat r;
    r.a11=(v.a11*v.a11+v.a12*v.a21+v.a13*v.a31)%mod;
    r.a12=(v.a11*v.a12+v.a12*v.a22+v.a13*v.a32)%mod;
    r.a13=(v.a11*v.a13+v.a12*v.a23+v.a13*v.a33)%mod;
    r.a21=(v.a21*v.a11+v.a22*v.a21+v.a23*v.a31)%mod;
    r.a22=(v.a21*v.a12+v.a22*v.a22+v.a23*v.a32)%mod;
    r.a23=(v.a21*v.a13+v.a22*v.a23+v.a23*v.a33)%mod;
    r.a31=(v.a31*v.a11+v.a32*v.a21+v.a33*v.a31)%mod;
    r.a32=(v.a31*v.a12+v.a32*v.a22+v.a33*v.a32)%mod;
    r.a33=(v.a31*v.a13+v.a32*v.a23+v.a33*v.a33)%mod;
    v=r;
    if(p%2==1)
    {
        r.a11=(v.a11*a+v.a12)%mod;
        r.a12=(v.a11*b+v.a13)%mod;
        r.a13=(v.a11*c)%mod;

         r.a21=(v.a21*a+v.a22)%mod;
        r.a22=(v.a21*b+v.a23)%mod;
        r.a23=(v.a21*c)%mod;

         r.a31=(v.a31*a+v.a32)%mod;
        r.a32=(v.a31*b+v.a33)%mod;
        r.a33=(v.a31*c)%mod;
    }
    return r;
}
int main()
{
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);

    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        scanf("%d%d%d%d%d%d%d",&x,&y,&z,&a,&b,&c,&n);
        init.a11=a;init.a12=b;init.a13=c;
        init.a21=init.a32=1;
        init.a22=init.a23=init.a31=init.a33=0;
        mat sol=lg_pow(n-2);
        solf=(sol.a11*z+sol.a12*y+sol.a13*x)%mod;
        printf("%d\n",solf);


    }
}