#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[4][4];
unsigned long long R[4][4];
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[4][4];

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

short binary_length;
long long mask;
 pas;
long long nc;
unsigned long long suma;

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);
            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) {
//                    R[i][j] = C[i][j];
//                }
//            }
        }

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

            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) {
//                    R[i][j] = C[i][j];
//                }
//            }
        }

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

    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;

        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;


//        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) {
//
//}

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