#include<cstdio>
using namespace std;
int t,a,x,y,z,b,c,n;
long long a1[5][5],a2[5][5],rez[5][5];

void inm(){//rez*a1
    long long fin[5][5];
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            fin[i][j]=0;
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            for(int k=1;k<=3;k++)
                fin[i][j]=(fin[i][j]+((rez[i][k]*a1[k][j]))%666013)%666013;
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            rez[i][j]=fin[i][j];
}

void inm2(){//rez*rez
    long long fin[5][5];
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            fin[i][j]=0;
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            for(int k=1;k<=3;k++)
                fin[i][j]=(fin[i][j]+((rez[i][k]*rez[k][j]))%666013)%666013;
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            rez[i][j]=fin[i][j];
}


void inm3(){//rez*a2
    long long fin[5][5];
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            fin[i][j]=0;
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            for(int k=1;k<=3;k++)
                fin[i][j]=(fin[i][j]+((rez[i][k]*a2[k][j]))%666013)%666013;
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            rez[i][j]=fin[i][j];
}



void ridic(int put){//ridic a1 la puterea n
    //rez = a1;
    if(put>1){
        if(put%2==1){
            ridic(put-1);
            inm();//rez*a1
        }
        else{
        ridic(put/2);
        inm2();//rez*rez
        }
    }
}




int main(){
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    scanf("%d",&t);
    a1[1][2]=1;
    a1[2][3]=1;
    for(int i=1;i<=t;i++){
        scanf("%d%d%d%d%d%d%d",&x,&y,&z,&a,&b,&c,&n);
        n-=2;
        a1[3][1]=c;
        a1[3][2]=b;
        a1[3][3]=a;
        for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            rez[i][j]=a1[i][j];
        ridic(n);
        a2[1][1]=x;
        a2[2][1]=y;
        a2[3][1]=z;
        inm3();//rez*a2
        printf("%lld\n",rez[3][1]);
    }
    return 0;
}