#include<fstream>
using namespace std;
ifstream F("iepuri.in");
ofstream G("iepuri.out");
#define F(i) for(int i=0;i<3;++i)
#define L long long
int t,x,y,z,n,M=666013;
struct X {
    L A[3][3];
    L* operator[](int i)
    {
        return A[i];
    }
    X operator*(X B)
    {
        X C={};
        F(i) F(j) F(k) (C[i][j]+=A[i][k]*B[k][j])%=M;
        return C;
    }
};
X Z,R;
int main()
{
    for(F>>t;t--;G<<(X{{{x,y,z}}}*R)[0][0]<<'\n')
        for(Z={{{},{1},{0,1}}},R={{{1},{0,1},{0,0,1}}},F>>x>>y>>z>>Z[2][2]>>Z[1][2]>>Z[0][2]>>n;n;n>>=1,Z=Z*Z)
            if(n&1)
                R=R*Z;
    return 0;
}