#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

#define MOD 666013
int x,y,z,a,b,c,n,A[3][3],B[3][1],tmp[3][3],tmp2[3][1],t;

void open(){
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
}

void add(int &a,int b){
    a+=b;
    if (a>=MOD) a%=MOD;
}

int main(){
    open();
    scanf("%d",&t);
    while (t--){
        scanf("%d%d%d%d%d%d%d",&x,&y,&z,&a,&b,&c,&n);
        A[0][0]=a;A[0][1]=b;A[0][2]=c;
        A[1][0]=1;A[1][1]=0;A[1][2]=0;
        A[2][0]=0;A[2][1]=1;A[2][2]=0;
        B[0][0]=z;
        B[1][0]=y;
        B[2][0]=x;
        n-=2;
        while (n){
            if (n&1){
                for (int i=0;i<3;i++){
                    for (int j=0;j<1;j++){
                        tmp2[i][j]=0;
                        for (int k=0;k<3;k++){
                            add(tmp2[i][j],(A[i][k]*B[k][j])%MOD);
                        }
                    }
                }
                memcpy(B,tmp2,sizeof(tmp2));
                n--;
            }
            for (int i=0;i<3;i++){
                for (int j=0;j<3;j++){
                    tmp[i][j]=0;
                    for (int k=0;k<3;k++){
                        add(tmp[i][j],A[i][k]*A[k][j]);
                    }
                }
            }
            memcpy(A,tmp,sizeof(A));
            n>>=1;
        }
        printf("%d\n",B[0][0]);
    }
    return 0;
}