#include <fstream>

using namespace std;

ifstream fin("iepuri.in");
ofstream fout("iepuri.out");

const int mod=666013, mmax=3;

int v1[mmax][mmax], v2[mmax][mmax], sol[mmax], s[mmax];

void zero(int x, int y, int z, int a, int b, int c){
    for(int i=0;i<mmax;i++){
        for(int j=0;j<mmax-1;j++){
            v1[i][j]=0;
        }
    }
    v1[1][0]=1;
    v1[2][1]=1;
    v1[0][2]=c;
    v1[1][2]=b;
    v1[2][2]=a;
    sol[0]=x;
    sol[1]=y;
    sol[2]=z;
    return;
}

void solve(){
    int x,y,z,a,b,c,n;
    fin>>x>>y>>z>>a>>b>>c>>n;
    zero(x,y,z,a,b,c);
    for(int in=1;in<=n;in*=2){
        if((in&n)!=0){
            for(int i=0;i<mmax;i++){
                s[i]=0;
                for(int j=0;j<mmax;j++){
                    s[i]=(s[i]+sol[j]*v1[j][i])%mod;
                }
            }
            for(int i=0;i<mmax;i++){
                sol[i]=s[i];
                s[i]=0;
            }
        }
        for(int i=0;i<mmax;i++){
            for(int k=0;k<mmax;k++){
                for(int j=0;j<mmax;j++){
                    v2[i][k]=(v2[i][k]+v1[i][j]*v1[j][k])%mod;
                }
            }
        }
        for(int i=0;i<mmax;i++){
            for(int j=0;j<mmax;j++){
                v1[i][j]=v2[i][j];
                v2[i][j]=0;
            }
        }
    }
    fout<<sol[0]<<"\n";
    return;
}

int main(){
    int t;
    fin>>t;
    while(t>0){
        t--;
        solve();
    }
    return 0;
}