#include <cstdio>
#define mod 666013
using namespace std;

struct matrice {
    unsigned int a11,a12,a13,a21,a22,a23,a31,a32,a33;
};

matrice nul;
unsigned int t,x,y,z,a,b,c,n;

inline matrice multmat(matrice &a,matrice &b) {
    matrice r;
    r.a11 = ((a.a11*b.a11)%mod + (a.a12*b.a21)%mod + (a.a13*b.a31)%mod)%mod;
    r.a12 = ((a.a11*b.a12)%mod + (a.a12*b.a22)%mod + (a.a13*b.a32)%mod)%mod;
    r.a13 = ((a.a11*b.a13)%mod + (a.a12*b.a23)%mod + (a.a13*b.a33)%mod)%mod;
    r.a21 = ((a.a21*b.a11)%mod + (a.a22*b.a21)%mod + (a.a23*b.a31)%mod)%mod;
    r.a22 = ((a.a21*b.a12)%mod + (a.a22*b.a22)%mod + (a.a23*b.a32)%mod)%mod;
    r.a23 = ((a.a21*b.a13)%mod + (a.a22*b.a23)%mod + (a.a23*b.a33)%mod)%mod;
    r.a31 = ((a.a31*b.a11)%mod + (a.a32*b.a21)%mod + (a.a33*b.a31)%mod)%mod;
    r.a32 = ((a.a31*b.a12)%mod + (a.a32*b.a22)%mod + (a.a33*b.a32)%mod)%mod;
    r.a32 = ((a.a31*b.a13)%mod + (a.a32*b.a23)%mod + (a.a33*b.a33)%mod)%mod;
    return r;
}

matrice putlog(matrice a,int p) {
    if (p == 1) return a;
    matrice aux = putlog(a,p/2);
    matrice r = multmat(aux,aux);
    if (p%2 == 1) {
        aux = r;
        r = multmat(aux,a);
    }
    return r;
}

int main() {
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    scanf("%u",&t);
    while (t--) {
        scanf("%u %u %u %u %u %u %u",&x,&y,&z,&a,&b,&c,&n);
        matrice init = nul;
        init.a11 = a;
        init.a12 = b;
        init.a13 = c;
        init.a21 = 1;
        init.a32 = 1;
        init = putlog(init,n-2);
        matrice s = nul;
        s.a11 = z;
        s.a21 = y;
        s.a31 = x;
        matrice x = multmat(init,s);
        printf("%u\n",x.a11);
    }
    return 0;
}