#include <bits/stdc++.h>

std::ifstream fin("iepuri.in");
std::ofstream fout("iepuri.out");

const int MOD = 666013;
const int INF = 1e9 + 5;
const int64_t LONG_INF = static_cast<int64_t>(1e18) + 5;

struct matrix {
    std::vector<std::vector<int64_t>> mat = std::vector<std::vector<int64_t>>(4, std::vector<int64_t>(4, 0));

    void identity() {
        for (int i = 1; i <= 3; ++i) {
            for (int j = 1; j <= 3; ++j) {
                mat[i][j] = 0;
            }
        }
        mat[1][1] = mat[2][2] = mat[3][3] = 1;
    }

    matrix operator*(const matrix &A) const {
        matrix C;
        for (int i = 1; i <= 3; ++i) {
            for (int j = 1; j <= 3; ++j) {
                for (int k = 1; k <= 3; ++k) {
                    C.mat[i][j] = (C.mat[i][j] + mat[i][k] * A.mat[k][j]) % MOD;
                }
            }
        }
        return C;
    };
};

matrix log_exp(matrix A, int exponent) {
    matrix res;
    res.identity();
    while (exponent) {
        if (exponent & 1) {
            res = res * A;
        }
        A = A * A;
        exponent /= 2;
    }
    return res;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q, x, y, z, a, b, c;

    fin >> q;
    while (q--) {
        fin >> x >> y >> z >> a >> b >> c >> n;
        // matrixes initialization, T = column matrix, DELTA = factors matrix
        matrix T, DELTA;
        T.mat[1][1] = x;
        T.mat[2][1] = y;
        T.mat[3][1] = z;
        //DELTA.mat[1][1] = DELTA.mat[1][3] = DELTA.mat[2][1] = DELTA.mat[2][2] = 0;
        DELTA.mat[1][2] = DELTA.mat[2][3] = 1;
        DELTA.mat[3][1] = c;
        DELTA.mat[3][2] = b;
        DELTA.mat[3][3] = a;

        matrix ANS = log_exp(DELTA, n) * T;
        fout << ANS.mat[1][1] << "\n";
    }

    return 0;
}