#include<fstream>
using namespace std;
ifstream f("iepuri.in");
ofstream g("iepuri.out");

int mod=666013;

struct Matrice
{
    long long a00,a01,a02,a10,a11,a12,a20,a21,a22;
};

Matrice inmultireMatrici(Matrice A, Matrice B)
{
    Matrice C;

    C.a00 = (A.a00 * B.a00 + A.a01* B.a10+ A.a02 * B.a20) % mod;
    C.a01 = (A.a00 * B.a01 + A.a01* B.a11+ A.a02 * B.a21) % mod;
    C.a02 = (A.a00 * B.a02 + A.a01* B.a12+ A.a02 * B.a22) % mod;
    C.a10 = (A.a10 * B.a00 + A.a11* B.a10+ A.a12 * B.a20) % mod;
    C.a11 = (A.a10 * B.a01 + A.a11* B.a11+ A.a12 * B.a21) % mod;
    C.a12 = (A.a10 * B.a02 + A.a11* B.a12+ A.a12 * B.a22) % mod;
    C.a20 = (A.a20 * B.a00 + A.a21* B.a10+ A.a22 * B.a20) % mod;
    C.a21 = (A.a20 * B.a01 + A.a21* B.a11+ A.a22 * B.a21) % mod;
    C.a22 = (A.a20 * B.a02 + A.a21* B.a12+ A.a22 * B.a22) % mod;

    return C;
}

Matrice putere(Matrice M, long long k)
{
    Matrice R;
    R.a00 = 1;
    R.a01 = 0;
    R.a02 = 0;
    R.a10 = 0;
    R.a11 = 1;
    R.a12 = 0;
    R.a20 = 0;
    R.a21 = 0;
    R.a22 = 1;

    while(k!=0)
    {
        if(k%2==1)
        {
            R = inmultireMatrici(R, M);
        }

        M = inmultireMatrici(M, M);
        k/=2;
    }

    return R;
}
int main()
{
    long long n,x,y,z,a,b,c,t,i;
    f>>t;

    for(i=1; i<=t; i++)
    {
        f>>x>>y>>z>>a>>b>>c>>n;
        Matrice M;
        Matrice W;
        M.a00 = 0;
        M.a01 = 1;
        M.a02 = 0;
        M.a10 = 0;
        M.a11 = 0;
        M.a12 = 1;
        M.a20 = c;
        M.a21 = b;
        M.a22 = a;

        W.a00 = x;
        W.a01 = 0;
        W.a02 = 0;
        W.a10 = y;
        W.a11 = 0;
        W.a12 = 0;
        W.a20 = z;
        W.a21 = 0;
        W.a22 = 0;



        Matrice rezultat = putere(M, n-2);
        rezultat=inmultireMatrici(rezultat,W);

        g<<rezultat.a20<< '\n';
    }

    return 0;
}