#include<fstream>

using namespace std;

ifstream cin("iepuri.in");
ofstream cout("iepuri.out");

long long I[4][4],F[4][2],rez[4][4],Ifin[4][4];
int x,y,z,a,b,c,t,n;

void init(){
    I[1][2]=I[2][3]=1;
    I[3][1]=c;
    I[3][2]=b;
    I[3][3]=a;
    I[1][1]=I[1][3]=I[2][1]=I[2][2]=0;

    F[1][1]=x;
    F[2][1]=y;
    F[3][1]=z;

    Ifin[1][1]=Ifin[2][2]=Ifin[3][3]=1;
    Ifin[1][2]=Ifin[1][3]=Ifin[2][1]=Ifin[2][3]=Ifin[3][1]=Ifin[3][2]=0;
}
void reset(){
     for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            rez[i][j]=0;
}
void prod_Ifin_I(){
    reset();
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++)
            for(int k=1;k<=3;k++)
                rez[i][j]+=Ifin[i][k]*I[k][j];
    }
}
void prod_I_I(){
    reset();
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++)
            for(int k=1;k<=3;k++)
                rez[i][j]+=I[i][k]*I[k][j];
    }
}
void prod_Ifin_F(){
    reset();
    for(int i=1;i<=3;i++){
        for(int j=1;j<=1;j++)
            for(int k=1;k<=3;k++)
                rez[i][j]+=Ifin[i][k]*F[k][j];
    }
}
void sch_Ifin(){
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            Ifin[i][j]=rez[i][j]%666013;
}
void sch_I(){
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            I[i][j]=rez[i][j]%666013;
}
void power(int b){
    while(b!=0){
        if(b%2==1){
            prod_Ifin_I();
            sch_Ifin();
            b--;
        }
        else{
            prod_I_I();
            sch_I();
            b=b/2;
        }
    }
}
int main(){
    cin>>t;
    for(int q=1;q<=t;q++){
        cin>>x>>y>>z>>a>>b>>c>>n;
        init();
        power(n-2);
        prod_Ifin_F();
        cout<<rez[3][1]%666013<<endl;
    }
    return 0;
}