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

void inm(){//rez*a1
    int 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
    int 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
    int 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(){//ridic a1 la puterea n
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            rez[i][j]=a1[i][j];
    //rez = a1;
    int put=n;
        while(put!=1){
            if(put%2==0){
                inm2();//rez*rez
                put/=2;
            }
            if(put>1&&put%2==1){
                inm2();//rez*rez
                put=(put-1)/2;
                inm();//rez*a1
            }
        }
        /*if(put%2==1){
            inm();//rez*a1
            put--;
        }
        else
        if(put>0){
            inm2();//rez*rez
            put/=2;
        }*/
    }





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;
        ridic();
        a2[1][1]=x;
        a2[2][1]=y;
        a2[3][1]=z;
        inm3();//rez*a2
        printf("%d\n",rez[3][1]);
    }
    return 0;
}