#include <iostream>
#include <fstream>

#define N 666013

using namespace std;

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

void populare(int, int, int, int, int, int);
//short base2_length(int);

/// Matricea ajutatoare, A, si vectorul initial, V.
unsigned long long A[5][5];
unsigned long long R[5][5];
int V[5];

/// Numarul de seturi de date.
int t;
/// Iepurii din zilele 0, 1 si 2.
int x, y, z;
/// Coeficientii termenilor recursivitatiii.
int a, b, c;
/// Numarul de zile in care iepurii se inmultesc
int n;

int C[5][5];

void inmulteste(unsigned long long a[5][5], unsigned long long b[5][5],
                unsigned long long result[5][5]) {

}

short binary_length;
int mask;
int pas;
int nc;

int exponentiere(int n) {
    binary_length = 0;
    pas = 0;
    nc = n;

    // TESTAT - arata bine
//    cerr << "num " << n << "  ";
//    cerr << "blen " << binary_length << "\n";

    while (nc != 0) {
        ++binary_length;
        nc = nc >> 1;
    }

    mask = 1 << binary_length;

    while (mask != 0) {
        if (pas != 1) {
            //inmulteste(R, R, R);
            unsigned long long suma = 0;

            /// Linia din C
            for (int i = 1; i <= 3; ++i) {
                /// Coloana din C
                for (int j = 1; j <= 3; ++j) {

                    suma = 0;
                    for (int h = 1; h <= 3; ++h) {
                        suma += (R[i][h]*R[h][j]) % N;
                    }

                    C[i][j] = suma % N;
                }
            }

        //    for (int i = 1; i <= 3; ++i) {
        //        for (int j = 1; j <= 3; ++j) {
        //            result[i][j] = C[i][j];
        //        }
        //    }
        }

        if (mask & n) {
            inmulteste(R, A, R);

            unsigned long long suma = 0;

            /// Linia din C
            for (int i = 1; i <= 3; ++i) {
                /// Coloana din C
                for (int j = 1; j <= 3; ++j) {

                    suma = 0;
                    for (int h = 1; h <= 3; ++h) {
                        suma += (R[i][h]*A[h][j]) % N;
                    }

                    C[i][j] = suma % N;
                }
            }

        //    for (int i = 1; i <= 3; ++i) {
        //        for (int j = 1; j <= 3; ++j) {
        //            result[i][j] = C[i][j];
        //        }
        //    }
        }

        ++pas;
        mask = mask >> 1;
    }

    int suma = ((R[1][1]*V[3]%N + R[1][2]*V[2]%N)%N + R[1][3]*V[1]%N) % N;
    return suma;
}

//int inmultire_finala(unsigned long long a[5][5], int v[5]) {
//    int suma;
//}

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

        populare(a, b, c, x, y, z);
        g << exponentiere(n - 2) << "\n";
//        g << inmultire_finala(R, V) << "\n";

//        for (int i = 1; i <= 3; ++i) {
//            for (int j = 1; j <= 3; ++j) {
//                g << R[i][j] << " ";
//            }
//            g << "\n";
//        }
//        g << "\n";

//        cerr << x << " ";
//        cerr << y << " ";
//        cerr << z << " ";
//        cerr << a << " ";
//        cerr << b << " ";
//        cerr << c << " ";
//        cerr << n << "\n";
    }

    f.close();
    g.close();
    return 0;
}

void populare(int a, int b, int c, int x, int y, int z) {
    A[1][1] = a;
    A[1][2] = b;
    A[1][3] = c;

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

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

    V[1] = x;
    V[2] = y;
    V[3] = z;

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

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

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

}

//inline short base2_length(int n) {
//    short length = 0;
//    while (n != 0) {
//        ++length;
//        n = n >> 1;
//    }
//    return length;
//}