#include<cstdio>
#define M 666013
#define N 3
using namespace std;

class mat{
public:
    int A[N][N];

    mat(){
        int i,j;
        for(i=0;i<N;i++)
            for(j=0;j<N;j++)
                A[i][j]=0;
    }

    void fill(int a,int b,int c){
        A[0][0]=a;
        A[0][1]=b;
        A[0][2]=c;
        A[1][0]=A[2][1]=1;
        A[1][1]=A[1][2]=A[2][0]=A[2][2]=0;
    }

    mat operator *(mat B){
        mat C;
        int i,j,l;

        for(i=0;i<N;i++)
            for(j=0;j<N;j++)
                for(l=0;l<N;l++){
                    C.A[i][j]+=((1LL*B.A[i][l]*A[l][j])%M)-M;
                    if (C.A[i][j]<0) C.A[i][j]+=M;
                }

        return C;
    }
};

mat pow(mat A,int n){
    if (n==1) return A;

    if (n&1) return A*pow(A,n-1);
    return pow(A*A,n/2);
}

int main(){
    freopen ("iepuri.in","r",stdin);
    freopen ("iespuri.out","w",stdout);
    int t,n;
    int x,y,z;
    int a,b,c;
    mat A;

    scanf ("%d",&t);

    for(;t>0;t--){
        scanf ("%d%d%d",&a,&b,&c);
        scanf ("%d%d%d",&x,&y,&z);
        scanf ("%d",&n);

        A.fill(a,b,c);
        A=pow(A,n-2);

        printf ("%lld\n",(1LL*z*A.A[0][0]+1LL*y*A.A[0][1]+1LL*x*A.A[0][2])%M);
    }

    return 0;
}