#include <cstdio>
#define MOD 666013

int main(){
    FILE*fi,*fout;
    long long B1,B2,B3,B4,B5,B6,B7,B8,B9,aux1,aux2,aux3,aux4,aux5,aux6,aux7,aux8,aux9,x,y,z,a,b,c,pr1,pr2,pr3,pr4,pr5,pr6,pr7,pr8,pr9;
    int n,t;
    fi=fopen("iepuri.in" ,"r");
    fout=fopen("iepuri.out" ,"w");
    fscanf(fi,"%d" ,&t);
    while(t){
        t--;
        fscanf(fi,"%lld%lld%lld%lld%lld%lld%d" ,&x,&y,&z,&a,&b,&c,&n);
        n-=2;
        B1=B2=B5=B7=0;
        B4=B8=1;
        B3=c;
        B6=b;
        B9=a;
        pr1=pr5=pr9=1;
        pr2=pr3=pr4=pr6=pr7=pr8=0;
        while(n){
            if(n&1){
                aux1=pr1*B1+pr2*B4+pr3*B7;
                aux2=pr1*B2+pr2*B5+pr3*B8;
                aux3=pr1*B3+pr2*B6+pr3*B9;
                aux4=pr4*B1+pr5*B4+pr6*B7;
                aux5=pr4*B2+pr5*B5+pr6*B8;
                aux6=pr4*B3+pr5*B6+pr6*B9;
                aux7=pr7*B1+pr8*B4+pr9*B7;
                aux8=pr7*B2+pr8*B5+pr9*B8;
                aux9=pr7*B3+pr8*B6+pr9*B9;
                pr1=aux1%MOD; pr2=aux2%MOD; pr3=aux3%MOD; pr4=aux4%MOD; pr5=aux5%MOD; pr6=aux6%MOD; pr7=aux7%MOD; pr8=aux8%MOD; pr9=aux9%MOD;
            }
            n>>=1;
            aux1=B1*B1+B2*B4+B3*B7;
            aux2=B1*B2+B2*B5+B3*B8;
            aux3=B1*B3+B2*B6+B3*B9;
            aux4=B4*B1+B5*B4+B6*B7;
            aux5=B4*B2+B5*B5+B6*B8;
            aux6=B4*B3+B5*B6+B6*B9;
            aux7=B7*B1+B8*B4+B9*B7;
            aux8=B7*B2+B8*B5+B9*B8;
            aux9=B7*B3+B8*B6+B9*B9;
            B1=aux1%MOD; B2=aux2%MOD; B3=aux3%MOD; B4=aux4%MOD; B5=aux5%MOD; B6=aux6%MOD; B7=aux7%MOD; B8=aux8%MOD; B9=aux9%MOD;
        }
        fprintf(fout,"%lld\n" ,(x*pr3+y*pr6+z*pr9)%MOD);
    }
    fclose(fi);
    fclose(fout);
    return 0;
}