#include <fstream>

long long int rez[4][4];
long long int v[4][4];
long long int vtmp[4][4];
long long int tmp[4][4];
long long int T;
long long int X,Y,Z,A,B,C,i,j,k, N;
using namespace std;

int mod = 666013;

int main()
{
    ifstream f("iepuri.in");
    ofstream g("iepuri.out");
    f >> T;
    while(T)
    {
        f >> X >> Y >> Z >> A >> B >> C >> N;
        v[1][1] = Z;
        v[2][1] = Y;
        v[3][1] = X;
        rez[1][1] = A;
        rez[1][2] = B;
        rez[1][3] = C;
        rez[2][1] = 1;
        rez[2][2] = 0;
        rez[2][3] = 0;
        rez[3][1] = 0;
        rez[3][2] = 1;
        rez[3][3] = 0;
        N -= 2;
        while(N)
        {
            if(N%2)
            {
                for(i = 1; i <= 3; i++)
                    for(j = 1; j <= 3; j++)
                        for ( k = 1; k <= 3; k++)
                            vtmp[i][j] += rez[i][k] * v[k][j];
                v[1][1] = vtmp[1][1] % mod;
                v[2][1] = vtmp[2][1] % mod;
                v[3][1] = vtmp[3][1] % mod;
                for ( i = 1; i <= 3; i++)
                    for ( j = 1; j <= 3; j++)
                        vtmp[i][j] = 0;
            }

            for ( i = 1; i <= 3; i++)
            {
                for ( j = 1; j <= 3; j++)
                {
                    for ( k = 1; k <= 3; k++)
                    {
                        tmp[i][j] += rez[i][k] * rez[k][j];
                    }
                }
            }
            for ( i = 1; i <= 3; i++)
                for ( j = 1; j <= 3; j++)
                {
                    rez[i][j] = tmp[i][j] % mod;
                    tmp[i][j] = 0;
                }
            N /= 2;
        }
        g << v[1][1] << '\n';
        T--;
    }
    f.close();
    g.close();



    return 0;
}