#include <fstream>
using namespace std;

long long inm[3][3];
void inmulteste_matrici(long long prima[3][3],long long doua[3][3])
{
    int i,j,k;
    for(i=0;i<3;++i)
        for (j=0;j<3;++j)
            inm[i][j]=0;

    for(i=0;i<3;++i)
        for(j=0;j<3;++j)
            for(k=0;k<3;++k)
                inm[i][j]=(doua[i][k] * prima[k][j] + inm[i][j]) % 666013;

    for(i=0;i<3;++i)
        for(j=0;j<3;++j)
            prima[i][j]=inm[i][j];
}

int main()
{
    long long mat1[3][3],mat2[3][3],n;
    ifstream f("iepuri.in");
    ofstream g("iepuri.out");
    int i,x,y,z,a,b,c,t;
    f>>t;

    for(i=1;i<=t;++i)
    {
        f >> x >> y >> z >> a >> b >> c >> n;

        mat1[0][1]=mat1[0][2]=mat1[1][1]=mat1[1][2]=mat1[2][1]=mat1[2][2]=0;
        mat1[2][0]=x;
        mat1[1][0]=y;
        mat1[0][0]=z;

        mat2[1][1]=mat2[1][2]=mat2[2][0]=mat2[2][2]=0;
        mat2[0][0]=a;
        mat2[0][1]=b;
        mat2[0][2]=c;
        mat2[1][0]=1;
        mat2[2][1]=1;

        n-=2;
        while (n != 0)
        {
            if(n % 2 == 1)
                inmulteste_matrici(mat1,mat2);
            inmulteste_matrici(mat2,mat2);
            n >>= 1;
        }
        g << mat1[0][0] << endl;
    }
    f.close();
    g.close();
    return 0;
}