#include <bits/stdc++.h>
std::ifstream fin("iepuri.in");
std::ofstream fout("iepuri.out");
#define MOD 666013
typedef long long ll;
struct mat{
    ll a, b, c, d, e, f, g, h, i;
};
ll x, y, z, a, b, c, n, t;
mat sol[35];
mat multiply(mat m1, mat m2);
int main()
{
    fin>>t;
    while(t--){
        fin>>x>>y>>z>>a>>b>>c>>n;
        sol[1]={0LL, 0LL, c, 1LL, 0LL, b, 0LL, 1LL, a};
        for(int i=2; i<=34; ++i) sol[i]=multiply(sol[i-1], sol[i-1]);
        n-=2;
        while(n){
            ll nr=int(log2(n));
            n=n-(1LL<<nr);
            ll ax, ay, az;
            ax=((x*sol[nr+1].a)%MOD+(y*sol[nr+1].d)%MOD+(z*sol[nr+1].g)%MOD)%MOD;
            ay=((x*sol[nr+1].b)%MOD+(y*sol[nr+1].e)%MOD+(z*sol[nr+1].h)%MOD)%MOD;
            az=((x*sol[nr+1].c)%MOD+(y*sol[nr+1].f)%MOD+(z*sol[nr+1].i)%MOD)%MOD;
            x=ax; y=ay; z=az;
        }
        fout<<z<<"\n";
    }
    return 0;
}
mat multiply(mat m1, mat m2){
    mat m;
    m.a=((m1.a*m2.a)%MOD+(m1.b*m2.d)%MOD+(m1.c*m2.g)%MOD)%MOD;
    m.b=((m1.a*m2.b)%MOD+(m1.b*m2.e)%MOD+(m1.c*m2.h)%MOD)%MOD;
    m.c=((m1.a*m2.c)%MOD+(m1.b*m2.f)%MOD+(m1.c*m2.i)%MOD)%MOD;
    m.d=((m1.d*m2.a)%MOD+(m1.e*m2.d)%MOD+(m1.f*m2.g)%MOD)%MOD;
    m.e=((m1.d*m2.b)%MOD+(m1.e*m2.e)%MOD+(m1.f*m2.h)%MOD)%MOD;
    m.f=((m1.d*m2.c)%MOD+(m1.e*m2.f)%MOD+(m1.f*m2.i)%MOD)%MOD;
    m.g=((m1.g*m2.a)%MOD+(m1.h*m2.d)%MOD+(m1.i*m2.g)%MOD)%MOD;
    m.h=((m1.g*m2.b)%MOD+(m1.h*m2.e)%MOD+(m1.i*m2.h)%MOD)%MOD;
    m.i=((m1.g*m2.c)%MOD+(m1.h*m1.f)%MOD+(m1.i*m2.i)%MOD)%MOD;
    return m;
}