#include<fstream>
using namespace std;
ifstream E("iepuri.in");
ofstream G("iepuri.out");
using L=long long;
const int M=666013;
#define F(i) for(int i=0;i<3;++i)
int t,x,y,z,n;
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;
    }
};
int main()
{
    E>>t;
    while(t--) {
        X Z={{{},{1},{0,1}}},R={{{1},{0,1},{0,0,1}}};
        E>>x>>y>>z>>Z[2][2]>>Z[1][2]>>Z[0][2]>>n;
        for(;n;n>>=1) {
            if(n&1)
                R=R*Z;
            Z=Z*Z;
        }
        G<<(X{{{x,y,z}}}*R)[0][0]<<'\n';
    }
    return 0;
}