#include <fstream>
using namespace std;
ifstream cin("iepuri.in");
ofstream cout("iepuri.out");
int t,x,y,z,a,b,c,n;
long long m[5][5];
void init_matrice(){
    int i,j;
    for(i=1;i<=4;i++)
        for(j=1;j<=4;j++)
            m[i][j]=0;
    m[1][2]=1;
    m[2][3]=1;
    m[3][4]=1;
    m[4][2]=c;
    m[4][3]=b;
    m[4][4]=a;
}
void ridic(int exp){
    int i,j,k;
    long long rez[5][5],aux[5][5];
    for(i=1;i<=4;i++)
        for(j=1;j<=4;j++){
        if(i==j)
            rez[i][j]=1;
        else
            rez[i][j]=0;
        aux[i][j]=0;
    }
    while(exp!=0){
        if(exp%2==0){
            exp=exp/2;
            for(i=1;i<=4;i++)
                for(j=1;j<=4;j++){
                    for(k=1;k<=4;k++)
                        aux[i][j]+=m[i][k]*m[k][j];
                    aux[i][j]=aux[i][j]%666013;
                }
            for(i=1;i<=4;i++)
                for(j=1;j<=4;j++){
                    m[i][j]=aux[i][j];
                    aux[i][j]=0;
                }
        }
        else{
            exp--;
            for(i=1;i<=4;i++)
                for(j=1;j<=4;j++){
                    for(k=1;k<=4;k++)
                        aux[i][j]+=rez[i][k]*m[k][j];
                    aux[i][j]=aux[i][j]%666013;
                }
            for(i=1;i<=4;i++)
                for(j=1;j<=4;j++){
                    rez[i][j]=aux[i][j];
                    aux[i][j]=0;
                }
        }
    }
    for(i=1;i<=4;i++)
        for(j=1;j<=4;j++)
            m[i][j]=rez[i][j];
}
int main()
{
    int i,iep;
    cin>>t;
    for(i=1;i<=t;i++){
        cin>>x>>y>>z>>a>>b>>c>>n;
        init_matrice();
        ridic(n-2);
        iep=(m[4][2]*x+m[4][3]*y+m[4][4]*z)%666013;
        cout<<iep<<'\n';
    }
    return 0;
}