#include <bits/stdc++.h>

using namespace std;

#define MOD 666013
#define ll long long

struct mat{
    ll a[3][3];

    inline void init(){
        int i,j;
        for (i=0;i<3;i++)
            for (j=0;j<3;j++)
                a[i][j]=0;
    }

    inline mat operator*(mat b){
        mat x;
        x.init();
        int i,j,k;
        for (i=0;i<3;i++)
            for (j=0;j<3;j++)
                for (k=0;k<3;k++)
                    x.a[i][j]=(x.a[i][j]+a[i][k]*b.a[k][j])%MOD;
        return x;
    }
}r,p,i3;

mat ptr(mat p, ll n){
    if (n==0) return i3;
    if (n==1) return p;
    mat x=ptr(p,n/2);
    x=x*x;
    if (n%2) x=x*p;
    return x;

}

int main()
{
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);

    ll t,a,b,c,x,y,z,n;
    i3.a[0][0]=1;
    i3.a[1][1]=1;
    i3.a[2][2]=1;
    scanf("%lld",&t);
    while (t){
        t--;
        scanf("%lld%lld%lld%lld%lld%lld%lld",&x,&y,&z,&a,&b,&c,&n);
        r.init();
        p.init();
        r.a[0][0]=x%MOD;
        r.a[0][1]=y%MOD;
        r.a[0][2]=z%MOD;
        p.a[1][0]=1;
        p.a[2][1]=1;
        p.a[0][2]=c%MOD;
        p.a[1][2]=b%MOD;
        p.a[2][2]=a%MOD;
        p=ptr(p,n);
        r=r*p;
        printf("%lld\n",r.a[0][0]);
    }
    return 0;
}