#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]) {
    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 += (a[i][h]*b[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];
//        }
//    }
}

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

void 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);
        }

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

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

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

    suma = ((a[1][1]*v[3]%N + a[1][2]*v[2]%N)%N + a[1][3]*v[1]%N) % N;

    return 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);
        exponentiere(n - 2);
        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;
//}