#include<fstream>
using namespace std;
ifstream F("iepuri.in");
ofstream G("iepuri.out");
#define H(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={};
        H(i) H(j) H(k) (c[i][j]+=a[i][k]*b[k][j])%=m;
        return c;
    }
};
X w,r;
int main()
{
    for(F>>t;t--;G<<(X{{{x,y,z}}}*r)[0][0]<<'\n')
        for(w={{{},{1},{0,1}}},r={{{1},{0,1},{0,0,1}}},F>>x>>y>>z>>w[2][2]>>w[1][2]>>w[0][2]>>n;n;n>>=1,w=w*w)
            if(n&1)
                r=r*w;
    return 0;
}