#include <fstream>
#include <cstring>
#define MOD 666013

using namespace std;

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

class Joc {
    private: int A,B,C,X,Y,Z,N;
    private: int M1[3][3],MX[3][3],AX[3][3],R[3][3];
    public: void setData (int a, int b, int c, int x, int y, int z, int n)
    {
        A=a;B=b;C=c;
        X=x;Y=y;Z=z;
        N=n-2;
    }

    private: void Multiply (int A[][3], int B[][3], int C[][3])
    {
        int i,j,k;
        for (i=0;i<3;i++)
            for (j=0;j<3;j++)
                C[i][j]=0;
        for (i=0;i<3;i++)
            for (j=0;j<3;j++)
                for (k=0;k<3;k++)
                    C[i][j]=(C[i][j]+A[i][k]*B[k][j])%MOD;

    }

    private: void LgPow (int P)
    {
        for (int i=0;i<3;i++)
            for (int j=0;j<3;j++)
                R[i][j]=0;
        R[0][0]=R[1][1]=R[2][2]=1;
        for (int i=1;i<=P;i<<=1)
        {
            if (i&P)
            {
                Multiply(R,MX,AX);
                memcpy(R,AX,sizeof(R));
            }
            Multiply(MX,MX,AX);
            memcpy(MX,AX,sizeof(MX));
        }
        memcpy(MX,R,sizeof(MX));
    }

    public: int Solve ()
    {
        M1[0][0]=Z;M1[0][1]=Y;M1[0][2]=X;
        M1[1][0]=0;M1[1][1]=0;M1[1][2]=0;
        M1[2][0]=0;M1[2][1]=0;M1[2][2]=0;
        MX[0][0]=A;MX[0][1]=1;MX[0][2]=0;
        MX[1][0]=B;MX[1][1]=0;MX[1][2]=1;
        MX[2][0]=C;MX[2][1]=0;MX[2][2]=0;
        LgPow(N);
        Multiply(M1,MX,AX);
        return AX[0][0];
    }
};

int T,n,x,y,z,a,b,c;

int main ()
{
    for (f >> T;T;--T)
    {
        f >> x >> y >> z >> a >> b >> c >> n;
        Joc G;
        G.setData(a,b,c,x,y,z,n);
        g << G.Solve() << '\n';
    }
    f.close();g.close();
    return 0;
}