#include <cstdint>
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

using Mat = vector<vector<int64_t>>;

Mat operator*(const Mat& a, const Mat& b) {
    constexpr int64_t kMod = 666013;

    int n = a.size();
    int l = a[0].size();
    int m = b[0].size();
    Mat res(n, vector<int64_t>(m, 0));
    for (int i = 0; i < n; i += 1) {
        for (int j = 0; j < m; j += 1) {
            for (int k = 0; k < l; k += 1) {
                res[i][j] += 1LL * a[i][k] * b[k][j];
                res[i][j] %= kMod;
            }
        }
    }
    return res;
}

Mat Eye(int64_t size) {
    Mat eye(size, vector<int64_t>(size, 0));
    for (int64_t i = 0; i < size; i += 1) {
        eye[i][i] = 1;
    }
    return eye;
}

Mat Power(const Mat& base, int64_t exp) {
    if (exp == 0) {
        return Eye(base.size());
    }
    if (exp == 1) {
        return base;
    }

    if (exp % 2 == 1) {
        return base * Power(base, exp - 1);
    }

    auto root = Power(base, exp / 2);
    return root * root;
}

int64_t Solve(const vector<int64_t>& init, const vector<int64_t>& mod, int64_t n) {
    if (n < 3) {
        return init[n];
    }

    Mat vec{{init[2]}, {init[1]}, {init[0]}};
    Mat mat{
        {mod[0], mod[1], mod[2]},
        {1, 0, 0},
        {0, 1, 0},
    };

    auto final_mat = Power(mat, n - 2);
    return (final_mat * vec)[0][0];
}

int main() {
    ifstream fin("iepuri.in");
    ofstream fout("iepuri.out");

    int tests;
    fin >> tests;

    for (int i = 0; i < tests; i += 1) {
        int64_t x, y, z;
        fin >> x >> y >> z;

        int64_t a, b, c;
        fin >> a >> b >> c;

        int64_t n;
        fin >> n;

        auto res = Solve({x, y, z}, {a, b, c}, n);
        fout << res << "\n";
    }
    return 0;
}