#include<cstdio>
#define mod 666013
using namespace std;
long long id[4][4],aux[4][4],m[4][4];
long long ridic_la_putere(long long x,long long y,long long z,long long a,long long b,long long c,long long exp){
    int i,j,k;
    long long rez[4][4];
    rez[1][1]=rez[2][2]=rez[3][3]=id[2][1]=id[3][2]=1;
    rez[1][2]=rez[1][3]=rez[2][1]=rez[2][3]=rez[3][1]=rez[3][2]=id[1][1]=id[1][2]=id[2][2]=id[3][1]=0;
    id[1][3]=c;
    id[2][3]=b;
    id[3][3]=a;
    m[1][1]=x;
    m[1][2]=y;
    m[1][3]=z;
    while(exp>0)
        if(exp%2==1){
            for(i=1;i<=3;i++)
                for(j=1;j<=3;j++)
                    aux[i][j]=rez[i][j];
            for(i=1;i<=3;i++)
                for(j=1;j<=3;j++){
                    rez[i][j]=0;
                    for(k=1;k<=3;k++)
                        rez[i][j]=(rez[i][j]+aux[i][k]*id[k][j])%mod;
                }
            exp--;
        }
        else{
            for(i=1;i<=3;i++)
                for(j=1;j<=3;j++)
                    aux[i][j]=id[i][j];
            for(i=1;i<=3;i++)
                for(j=1;j<=3;j++){
                    id[i][j]=0;
                    for(k=1;k<=3;k++)
                        id[i][j]=(id[i][j]+aux[i][k]*aux[k][j])%mod;
                }
            exp/=2;
        }
    for(j=1;j<=3;j++){
        aux[1][j]=0;
        for(k=1;k<=3;k++)
            aux[1][j]=(aux[1][j]+m[1][k]*rez[k][j])%mod;
    }
    return aux[1][3];
}
int main(){
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    int t,q;
    long long a,b,c,x,y,z,n;
    scanf("%d",&t);
    for(q=1;q<=t;q++){
        scanf("%lld%lld%lld%lld%lld%lld%lld",&x,&y,&z,&a,&b,&c,&n);
        printf("%lld\n",ridic_la_putere(x,y,z,a,b,c,n-2));
    }
    return 0;
}