#include<fstream>
using namespace std;
ifstream in("iepuri.in");
ofstream out("iepuri.out");
const long long MOD = 666013;

class MATRICE {

    int ln,cl;
    long long MAT[5][5];

    public:

    MATRICE(int linii,int coloane,long long V[][4])
    {

        ln = linii;
        cl = coloane;//0755 314 486 c negara
        for(int i = 0 ; i < ln ; ++i)
            for(int j = 0 ; j < cl ; ++j)
                MAT[i][j] = V[i][j];
    }
    MATRICE(int linii,int coloane,long long V[][2])
    {

        ln = linii;
        cl = coloane;//0755 314 486 c negara
        for(int i = 0 ; i < ln ; ++i)
            for(int j = 0 ; j < cl ; ++j)
                MAT[i][j] = V[i][j];
    }
    MATRICE(int linii,int coloane)
    {

        ln = linii;
        cl = coloane;
        for(int i = 0 ; i < ln ; ++i)
            for(int j = 0 ; j < cl ; ++j)
                MAT[i][j] = 0;
    }

    MATRICE operator*(MATRICE A)
    {

        MATRICE nou(this->ln,A.cl);
        for(int i = 0 ; i < this->ln ; ++i)
            for(int j = 0 ; j < A.cl ; ++j)
                for(int k = 0 ; k < this->cl ; ++k )
                    nou.MAT[i][j] = nou.MAT[i][j] + (1LL*this->MAT[i][k] * A.MAT[k][j]) % MOD;

        return nou;
    }

    void afis()
    {

        out<<MAT[0][0]<<"\n";
    }

};

long long T,A,B,C,X,Y,Z,N;

MATRICE pow(MATRICE INIT,long long e)
{
    long long UN[4][4] = {
        1,0,0,0,
        0,1,0,0,
        0,0,1,0,
        0,0,0,0
    };
    MATRICE rez(3,3,UN);
    while(e){
        if(e % 2){

            rez = rez * INIT;
            --e;
        }
        INIT = INIT * INIT;
        e /= 2;
    }
    return rez;
}

void solve()
{

    long long V[4][4] = {
        0 , 1 , 0,0,
        0 , 0 , 1,0,
        C , B , A,0,
        0,0,0,0
    };
    long long P[4][2] = {
        X,0,
        Y,0,
        Z,0,
        0,0
    };
    MATRICE M1(3,3,V);
    MATRICE M2(3,1,P);

    MATRICE R = pow(M1,N);

    R = R * M2;
    R.afis();
}

int main()
{

    in>>T;
    for( ; T ; --T){
        in>>X>>Y>>Z>>A>>B>>C>>N;
        solve();
    }
    return 0;
}