#include <fstream>
using namespace std;

ifstream fin ("iepuri.in");
ofstream fout ("iepuri.out");

int t, x, y, z, a, b, c, in[2][5], aj[5][5], r[2][5], n, rez;

int main()
{
    int nr, j, p, k;

    fin>>t;

    aj[1][1]=0;
    aj[2][1]=1;
    aj[3][1]=0;

    aj[1][2]=0;
    aj[2][2]=0;
    aj[3][2]=1;

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

        if (n>=3)
        {
            in[1][1]=x;
            in[1][2]=y;
            in[1][3]=z;

            aj[1][3]=c;
            aj[2][3]=b;
            aj[3][3]=a;

            for (nr=1; nr<=n-2; nr++)
            {
                for (k=1; k<=3; k++)
                {
                    for (j=1; j<=3; j++)
                    {
                        r[1][k]=(r[1][k]+(in[1][j]%666013*aj[j][k]%666013)%666013)%666013;
                    }
                }

                rez=r[1][3];

                for (j=1; j<=3; j++)
                {
                    in[1][j]=r[1][j];
                    r[1][j]=0;
                }
            }

             fout<<rez<<"\n";
        }
        else
        {
            if (n==0)
                fout<<x<<"\n";
            else
            {
                if (n==1)
                    fout<<y<<"\n";
                else
                {
                    fout<<z<<"\n";
                }
            }
        }
    }


    fin.close();
    fout.close();
    return 0;
}