#include <iostream>
#include <fstream>

using namespace std;

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

const int MOD = 666013;

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

struct matrix
{
    long long int m[3][3];
    matrix()
    {
        for (int i=0; i<3; i++)
        {
            for (int j=0; j<3; j++)
            {
                m[i][j] = 0;
            }
        }
    }
    matrix operator*(matrix b)
    {
        matrix c;

        for (int i=0; i<3; i++)
        {
            for (int j=0; j<3; j++)
            {
                for (int k=0; k<3; k++)
                {
                    c.m[i][j] = (c.m[i][j] + m[i][k]*b.m[k][j])%MOD;
                }
            }
        }
        return c;
    }
};

matrix start,initial,I;

matrix Ridica(int k)
{
    if (k == 0) return I;
    if (k == 1) return initial;
    matrix aux = Ridica(k/2);
    aux = aux * aux;
    if (k%2 == 1)
    {
        aux = aux * initial;
    }
    return aux;
}

int main()
{
    in >> t;
    I.m[0][0] = I.m[1][1] = I.m[2][2] = 1;
    while (t--)
    {
        in >> x >> y >> z >> a >> b >> c >> n;
        start.m[0][0] = x;
        start.m[0][1] = y;
        start.m[0][2] = z;

        initial.m[0][0] = 0;
        initial.m[0][1] = 0;
        initial.m[0][2] = c;

        initial.m[1][0] = 1;
        initial.m[1][1] = 0;
        initial.m[1][2] = b;

        initial.m[2][0] = 0;
        initial.m[2][1] = 1;
        initial.m[2][2] = a;

        matrix rasp = Ridica(n);
        rasp = start * rasp;
        out << rasp.m[0][0] << "\n";
    }
    return 0;
}