#include <iostream>
#include <vector>
#define MOD 666013

using namespace std;

int k, x, y, z, n;

class Matrice
{
private:
    vector <vector <int>> m;
    int len;
    void creeaza(int n)
    {
        len = n;
        m.clear();
        vector <int> push;
        for(int i=0;i<n;++i)
            push.push_back(0);
        for(int i=0;i<n;++i)
            m.push_back(push), m[i][i]=1;
    }
public:
    Matrice()
    {
        ;
    }

    Matrice(int n)
    {
        creeaza(n);
    }

    Matrice(vector<vector<int>> p, int n)
    {
        creeaza(n);
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
                m[i][j]=p[i][j];
    }

    Matrice& operator * (Matrice& b)
    {
        vector<vector<int>> p=m;
        for(int i=0;i<len;++i)
            for(int j=0;j<len;++j)
            {
                int rez=0;
                for(int k=0;k<len;++k)
                    rez+=m[i][k]*b.m[k][j], rez%=MOD;
                p[i][j]=rez;
            }
        Matrice rez(p,len);
        p.clear();
        return rez;
    }

    void afisare()
    {
        for(int i=0;i<len;++i)
        {
            for(int j=0;j<len;++j)
                cout<<m[i][j]<<" ";
            cout<<"\n";
        }
    }

    Matrice& operator = (Matrice&& b)
    {
        len = b.len;
        m=b.m;
        return *this;
    }

    Matrice& operator + (Matrice& b)
    {
        vector<vector<int>> p=m;

        for(int i=0;i<len;++i)
            for(int j=0;j<len;++j)
            {
                p[i][j]+=b.m[i][j];
            }
        Matrice rez(p,len);
        p.clear();
        return rez;
    }

    Matrice& operator += (Matrice& b)
    {
        for(int i=0;i<len;++i)
            for(int j=0;j<len;++j)
                m[i][j]+=b.m[i][j];
        return *this;
    }

    int get (int i, int j)
    {
        return m[i][j];
    }

    double set (int i, int j, double x)
    {
        m[i][j]=x;
        return m[i][j];
    }

    Matrice& operator *= (Matrice &b)
    {
        vector <vector <int> > p = m;
        for(int i=0;i<len;++i)
            for(int j=0;j<len;++j)
            {
                int rez=0;
                for(int k=0;k<len;++k)
                    rez+=(1LL*m[i][k]*b.m[k][j])%MOD, rez%=MOD;
                p[i][j]=rez;
            }
        m=p;
        return *this;
    }

    Matrice& operator ^ (int p)
    {
        Matrice rez(len);
        Matrice baza(m, len);
        while(p)
        {
            if(p%2==0)
                baza *= baza, p/=2;
            else
                rez *= baza, --p;
        }
        return rez;

    }

    Matrice& operator ^= (int p)
    {
        Matrice baza(m, len);
        creeaza(baza.len);
        while(p)
        {
            if(p%2==0)
                baza *= baza, p/=2;
            else
                *this *= baza, --p;
        }
        return *this;
    }
};

int main()
{
    freopen("iepuri.in", "r",stdin);
    freopen("iepuri.out", "w",stdout);
    vector <vector<int>>m;
    vector <int> aux(3);
    m.push_back(aux);
    aux[0]=1;
    m.push_back(aux);
    aux[0]=0;
    aux[1]=1;
    m.push_back(aux);
    cin>>k;
    for(int i=0;i<k;++i)
    {
        cin>>x>>y>>z>>m[0][0]>>m[0][1]>>m[0][2]>>n;
        Matrice a(m,3);
        a^=(n-2);
        long long rez=((1LL*a.get(0,0)*z)%MOD + (1LL*a.get(0,1)*y)%MOD + (1LL*a.get(0,2)*x)%MOD)%MOD;
        cout<<rez<<"\n";
    }
    return 0;
}