#include <iostream>
#include <fstream>
#define ull unsigned long long
#define mod 666013
using namespace std;

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

struct matrix {
    int n, m;
    int data[3][3] = {};
};

matrix assign(int n, int m) {
    matrix c;
    c.n = n;
    c.m = m;
    return c;
}

matrix multiply(const matrix &a, const matrix &b) {
    matrix c = assign(a.n, b.m);

    for (int i = 0; i < a.n; i++) {
        for (int j = 0; j < b.m; j++) {
            for (int k = 0; k < a.m; k++) {
                c.data[i][j] = (c.data[i][j] % mod + (a.data[i][k] % mod * (b.data[k][j] % mod)) % mod) % mod;
            }
        }
    }

    return c;
}

matrix I;

matrix fastExp(matrix base, ull pow) {
    if (pow == 0) {
        return I;
    }

    if (pow % 2 == 0) {
        matrix tmp = fastExp(base, pow / 2);
        return multiply(tmp, tmp);
    } else {
        return multiply(base, fastExp(base, pow - 1));
    }
}

int main() {
    int t;
    in >> t;

    I = assign(3, 3);
    for (int i = 0; i < I.n; i++) {
        I.data[i][i] = 1;
    }

    for (int q = 0; q < t; q++) {
        int X, Y, Z, A, B, C, N;
        in >> X >> Y >> Z >> A >> B >> C >> N;

        matrix M = assign(3, 3);
        matrix V = assign(3, 1);

        V.data[0][0] = Z;
        V.data[1][0] = Y;
        V.data[2][0] = X;

        M.data[0][0] = A;
        M.data[0][1] = B;
        M.data[0][2] = C;

        for (int i = 1; i < M.n; i++) {
            M.data[i][i - 1] = 1;
        }

        M = fastExp(M, N - 2);
        V = multiply(M, V);

        out << V.data[0][0] << '\n';
    }

}