#include <fstream>
#include <cstring>
#define mod 666013
using namespace std;
class matrice
{
    unsigned int m[3][3];
    public:
    void gol()
    {
        memset(m,0,sizeof(m));
    }
    void set_p(unsigned int a,unsigned int b,unsigned int c)
    {
        m[1][0]=m[2][1]=1;
        m[0][2]=c;m[1][2]=b;m[2][2]=a;
    }
    unsigned int r()
    {
        return m[0][2];
    }
    void set_u()
    {
        m[0][0]=m[1][1]=m[2][2]=1;
    }
    void sett(unsigned int x,unsigned int y,unsigned int z)
    {
        m[0][0]=x;m[0][1]=y;m[0][2]=z;
    }
    friend matrice operator*(matrice,matrice);
};
matrice operator* (matrice A,matrice B)
{
    matrice C;
    unsigned int i,j,k;
    for (i=0;i<=2;i++)
    {
        for (j=0;j<=2;j++)
        {
            C.m[i][j]=0;
            for (k=0;k<=2;k++)
            {
                C.m[i][j]+=(A.m[i][k]*B.m[k][j]);
            }
            C.m[i][j]%=mod;
        }
    }
    return C;
}
int main()
{
    ifstream f("iepuri.in");
    ofstream g("iepuri.out");
    long long n;
    matrice R,A;
    int t,i,x,y,z,a,b,c;
    f>>t;
    for (i=1;i<=t;i++)
    {
        f>>x>>y>>z>>a>>b>>c>>n;
        if (n<=2)
        {
            if (n==0) g<<x<<'\n';
            else
                if (n==1) g<<y<<'\n';
                else g<<z<<'\n';
        }
        else
        {
            n-=2;
            A.gol();R.gol();
            A.set_p(a,b,c);
            R.set_u();
            while (n)
            {
                if (n%2) R=R*A;
                A=A*A;
                n/=2;
            }
            A.gol();A.sett(x,y,z);
            A=A*R;
            g<<A.r()<<'\n';
        }
    }
    f.close();
    g.close();
    return 0;
}