#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll
#define MOD (666013)

ifstream fin("iepuri.in"); ofstream fout("iepuri.out");
#define cin fin
#define cout fout

int t, n, x, y, z, a, b, c;
int null[3][3];
int res[3][3];
int m[3][3];







void mat_exp(int e){
int m0[3][3];
for(int i=0; i<3; i++){
    for(int j=0; j<3; j++){
        m0[i][j]=(0+m[i][j]);
    }
}

if(e==0){
 return;
}
else{
    int pr[3]; pr[0]=0; pr[1]=0; pr[2]=0;
    int m1[3][3];
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            pr[j]=0;
            for(int g=0; g<3; g++){
                pr[j]+=(m[i][g]*m[g][j])%MOD;
            }
            pr[j]%=MOD;
        }
        for(int j=0; j<3; j++){
            m1[i][j]=pr[j];
        }
    }
    if( ( (int)(e/2) )>0 ){
        for(int i=0; i<3; i++){for(int j=0; j<3; j++){m[i][j]=m1[i][j];} } }
    mat_exp(e/2);
    pr[0]=0; pr[1]=0; pr[2]=0;
    if( ((e%2)==1) && ( ( (int)(e/2) )>0 )  ){
        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                pr[j]=0;
                for(int g=0; g<3; g++){
                    pr[j]+=(m[i][g]*m0[g][j])%MOD;
                }
                pr[j]%=MOD;
            }
            for(int j=0; j<3; j++){m1[i][j]=pr[j];}
        }
        for(int i=0; i<3; i++){for(int j=0; j<3; j++){m[i][j]=m1[i][j];} }
    }


}


return ;
}







int32_t main(){
INIT


cin>>t;
while(t--){
    cin>>x>>y>>z>>a>>b>>c>>n;
    res[0][0]=z; res[0][1]=y; res[0][2]=x;
    res[1][0]=0; res[1][1]=0; res[1][2]=0;
    res[2][0]=0; res[2][1]=0; res[2][2]=0;
    m[0][0]=a; m[0][1]=1; m[0][2]=0;
    m[1][0]=b; m[1][1]=0; m[1][2]=1;
    m[2][0]=c; m[2][1]=0; m[2][2]=0;
    mat_exp(n-2);

    for(int i=0; i<3; i++){
        int pr[3];
        for(int j=0; j<3; j++){
            pr[j]=0;
            for(int g=0; g<3; g++){
                pr[j]+=(res[i][g]*m[g][j])%MOD;
            }
            pr[j]%=MOD;
        }
        for(int j=0; j<3; j++){res[i][j]=pr[j];}
    }

    cout<<res[0][0]<<"\n";

}




return 0;
}