#include <iostream>
#include <fstream>
#define mod 666013
using namespace std;

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=v1;
        b1=1;
        b2=0;
        b3=v2;
        c1=0;
        c2=1;
        c3=v3;
    }

    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;
    }

    void afisare()
    {
        cout << a3;
    }

};

int main()
{
    int t,x,y,z,a,b,c,ziua;
    cin >> t;
    for (int i=1; i<t; i++)
    {
        cin >> 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;
}