#include <iostream>

#include <fstream>

#define mod 666013

using namespace std;

ifstream f("iepuri.in");
ofstream g("iepuri.out");

class matrice{



private:

    int a1,a2,a3,b1,b2,b3,c1,c2,c3;



public:

    matrice()

    {

        a1=1;

        b2=1;

        c3=1;

        a2=a3=b1=b3=c1=c2=0;

    }

    matrice(int v1, int v2, int v3)

    {

        a1=0;

        a2=0;

        a3=v3;

        b1=1;

        b2=0;

        b3=v2;

        c1=0;

        c2=1;

        c3=v1;

    }



    matrice(int v1, int v2, int v3, bool mat1)

    {

        a1=v1;

        a2=v2;

        a3=v3;

        b1=b2=b3=c1=c2=c3=0;

    }



    matrice ridicare_patrat()

    {

        int aa1=a1,aa2=a2,aa3=a3,ab1=b1,ab2=b2,ab3=b3,ac1=c1,ac2=c2,ac3=c3;

        a1=((aa1*aa1)%mod+(aa2*ab1)%mod+(aa3*ac1)%mod)%mod;

        a2=((aa1*aa2)%mod+(aa2*ab2)%mod+(aa3*ac2)%mod)%mod;

        a3=((aa1*aa3)%mod+(aa2*ab3)%mod+(aa3*ac3)%mod)%mod;

        b1=((ab1*aa1)%mod+(ab2*ab1)%mod+(ab3*ac1)%mod)%mod;

        b2=((ab1*aa2)%mod+(ab2*ab2)%mod+(ab3*ac2)%mod)%mod;

        b3=((ab1*aa3)%mod+(ab2*ab3)%mod+(ab3*ac3)%mod)%mod;

        c1=((ac1*aa1)%mod+(ac2*ab1)%mod+(ac3*ac1)%mod)%mod;

        c2=((ac1*aa2)%mod+(ac2*ab2)%mod+(ac3*ac2)%mod)%mod;

        c3=((ac1*aa3)%mod+(ac2*ab3)%mod+(ac3*ac3)%mod)%mod;

    }



    matrice &operator*=(const matrice nou_mat)

    {

        int aa1=a1,aa2=a2,aa3=a3,ab1=b1,ab2=b2,ab3=b3,ac1=c1,ac2=c2,ac3=c3;

        a1=((aa1*nou_mat.a1)%mod+(aa2*nou_mat.b1)%mod+(aa3*nou_mat.c1)%mod)%mod;

        a2=((aa1*nou_mat.a2)%mod+(aa2*nou_mat.b2)%mod+(aa3*nou_mat.c2)%mod)%mod;

        a3=((aa1*nou_mat.a3)%mod+(aa2*nou_mat.b3)%mod+(aa3*nou_mat.c3)%mod)%mod;

        b1=((ab1*nou_mat.a1)%mod+(ab2*nou_mat.b1)%mod+(ab3*nou_mat.c1)%mod)%mod;

        b2=((ab1*nou_mat.a2)%mod+(ab2*nou_mat.b2)%mod+(ab3*nou_mat.c2)%mod)%mod;

        b3=((ab1*nou_mat.a3)%mod+(ab2*nou_mat.b3)%mod+(ab3*nou_mat.c3)%mod)%mod;

        c1=((ac1*nou_mat.a1)%mod+(ac2*nou_mat.b1)%mod+(ac3*nou_mat.c1)%mod)%mod;

        c2=((ac1*nou_mat.a2)%mod+(ac2*nou_mat.b2)%mod+(ac3*nou_mat.c2)%mod)%mod;

        c3=((ac1*nou_mat.a3)%mod+(ac2*nou_mat.b3)%mod+(ac3*nou_mat.c3)%mod)%mod;
        return *this;

    }



    void afisare()

    {

        g << a3 << '\n';

    }



};



int main()

{

    int t,x,y,z,a,b,c,ziua;

    f >> t;

    for (int i=1; i<=t; i++)

    {

        f >> x >> y >> z >> a >> b >> c >> ziua;

        matrice mat1(x,y,z,true);

        matrice mat2(a,b,c);

        matrice mat3;

        ziua-=2;

        while (ziua)

        {

            if (ziua%2==0)

            {

                ziua/=2;

                mat2.ridicare_patrat();

            }

            else

            {

                ziua--;

                mat3*=mat2;

            }

        }

        mat1*=mat3;

        mat1.afisare();

    }

    return 0;

}