#include <fstream>

using namespace std;
ifstream cin("iepuri.in");
ofstream cout("iepuri.out");
int rez[4][4],i,j,k,sum,v[4][4],m[4][2],iep[4][2];

void ridic(int baza[4][4],int exp){
    for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
            rez[i][j]=(i==j);
    int aux[4][4];
    while(exp!=0){
        if(exp%2==0){
            exp/=2;
            for(i=1;i<=3;i++)
                for(j=1;j<=3;j++){
                    sum=0;
                    for(k=1;k<=3;k++)
                        sum=(sum+(1LL*baza[i][k]*baza[k][j]))%666013;
                    aux[i][j]=sum;
                }
            for(i=1;i<=3;i++)
                for(j=1;j<=3;j++)
                    baza[i][j]=aux[i][j];
        }
        else{
            exp--;
            for(i=1;i<=3;i++)
                for(j=1;j<=3;j++){
                    sum=0;
                    for(k=1;k<=3;k++)
                        sum=(sum+(1LL*rez[i][k]*baza[k][j]))%666013;
                    aux[i][j]=sum;
                }
            for(i=1;i<=3;i++)
                for(j=1;j<=3;j++)
                    rez[i][j]=aux[i][j];
        }
    }
}
int main()
{
    int x,y,z,a,b,c,t,g;
    long long n;
    cin>>t;
    for(g=1;g<=t;g++){
        cin>>x>>y>>z>>a>>b>>c>>n;
        for(i=1;i<=3;i++)
            for(j=1;j<=3;j++){
                rez[i][j]=0;
                iep[i][1]=0;
                v[i][j]=0;
                m[i][1]=0;
            }
        v[1][2]=1;
        v[2][3]=1;
        v[3][1]=c;
        v[3][2]=b;
        v[3][3]=a;
        m[1][1]=x;
        m[2][1]=y;
        m[3][1]=z;
        ridic(v,n-2);
        for(i=1;i<=3;i++){
            sum=0;
                for(k=1;k<=3;k++)
                    sum=(sum+(1LL*rez[i][k]*m[k][1]))%666013;
                iep[i][1]=sum;
        }
        cout<<iep[3][1]<<'\n';
    }
    return 0;
}