#include <iostream>
#include <fstream>

#define N 666013

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

using namespace std;

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];
        }
    }
}

void exponentiere(int n) {
    short binary_length = base2_length(n);
    int mask;
    int pas = 1;

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

    mask = 1 << binary_length - 1;

    while (mask != 0) {

        inmulteste(R, R, R);

        /// Primul bit e 1, sigur

//        if (pas == 1) {
//            inmulteste(R, A, R);
//            ++pas;
//            mask = mask >> 1;
//        }
//        else
            {
            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";
    }
    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;

}

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