#include<cstdio>
const int L=666013;
using namespace std;
long long c[4][4];
long long r[4][4],m[4][4];

void prod(long long a[4][4],long long b[4][4]) {
    int i,j,k;
    for(i=1; i<=3; i++)
        for(j=1; j<=3; j++) {
            c[i][j] = 0;
            for(k=1; k<=3; k++) {
                c[i][j]+=a[i][k]*b[k][j]%L;
                c[i][j] %= L;
            }
        }
    for(i=1; i<=3; i++)
        for(j=1; j<=3; j++) {
            a[i][j]=c[i][j];
        }
}
void raise(long long r[4][4],long long m[4][4],long long p) {
    if(p==0) return;
    if(p%2==0) {
        prod(m,m);
        raise(r,m,p/2);
    } else {
        prod(r,m);
        prod(m,m);
        raise(r,m,(p-1)/2);
    }
}
int main() {
    long long x,y,z,a,b,c;
    long long n;
    int t,te;
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    scanf("%d",&t);
    for(te=1; te<=t; te++) {
        scanf("%lld%lld%lld%lld%lld%lld%lld",&x,&y,&z,&a,&b,&c,&n);
        r[1][1]=1;
        r[1][2]=0;
        r[1][3]=0;
        r[2][2]=1;
        r[2][1]=0;
        r[2][3]=0;
        r[3][3]=1;
        r[3][1]=0;
        r[3][2]=0;
        m[1][1]=a;
        m[1][2]=b;
        m[1][3]=c;
        m[2][1]=1;
        m[2][2]=0;
        m[2][3]=0;
        m[3][1]=0;
        m[3][2]=1;
        m[3][3]=0;
        raise(r,m,n-2);
        long long sol;
        sol=(z*r[1][1]%L+y*r[1][2]%L+x*r[1][3]%L)%L;
        printf("%lld\n",sol);
    }
    return 0;
}