#include<fstream>
#include<vector>

using namespace std;

const char iname[]="iepuri.in";
const char oname[]="iepuri.out";
const int mod=666013;

ifstream f(iname);
ofstream g(oname);

class matrix
{
    private:
    int n,m;
    vector<vector<int> >a;
    public:
    matrix()
    {
        n=m=0;
    }
    matrix(int x,int y)
    {
        n=x;m=y;
        a.resize(n);
        for(int i=0;i<n;++i)
            a[i].resize(m);
    }
    void resize(int x,int y)
    {
        n=x;m=y;
        a.clear();
        a.resize(n);
        for(int i=0;i<n;++i)
            a[i].resize(m);
    }
    void operator=(const matrix& k)
    {
        this->resize(k.n,k.m);
        a=k.a;
    }
    vector<int> &operator[](const int& x)
    {
        return a[x];
    }
    matrix operator*(const matrix& d)
    {
        matrix k=d;
        int p=k.m;
        matrix aux(n,p);
        for(int i=0;i<n;++i)
            for(int j=0;j<p;++j)
                for(int r=0;r<m;++r)
                    aux[i][j]=(aux[i][j]+1LL*a[i][r]*k[r][j])%mod;

        return aux;
    }
} base(1,3),z(3,3),ans(3,3),aux;

int n,i,step,t,p;

int main()
{
    f>>t;
    z[1][0]=z[2][1]=1;
    for(p=1;p<=t;++p)
    {
        f>>base[0][0]>>base[0][1]>>base[0][2]>>z[2][2]>>z[1][2]>>z[0][2]>>n;
        ans.resize(3,3);
        ans[0][0]=ans[1][1]=ans[2][2]=1;
        aux=z;
        while(n)
        {
            if(n&1)
                ans=ans*aux;
            aux=aux*aux;
            n>>=1;
        }
        ans=base*ans;
        g<<ans[0][0]<<"\n";
    }

    f.close();
    g.close();

    return 0;
}