#include <fstream>
#include <vector>

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

typedef long long ll;
ll const MOD = 666013;

struct Matrix {
    int n, m;
    std::vector<std::vector<int>> mat;

    Matrix(int _n, int _m) {
        n = _n, m = _m;
        mat.resize(n);
        for (int i = 0; i < n; i++)
            mat[i].resize(m);
    }

    Matrix operator * (Matrix other) {
        Matrix ans(n, m);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                for (int k = 0; k < n; k++)
                    ans.mat[i][j] = (ans.mat[i][j] + (1LL * mat[i][k] * other.mat[k][j]) % MOD) % MOD;
        return ans;
    }
};

Matrix logPow(Matrix a, int b) {
    Matrix ans(a.n, a.m);
    for (int i = 0; i < ans.n; i++)
        ans.mat[i][i] = 1;
    while (b) {
        if (b & 1)
            ans = ans * a;
        a = a * a;
        b >>= 1;
    }
    return ans;
}

int main() {
    int t;
    fin >> t;
    while (t--) {
        int x, y, z, a, b, c, n;
        fin >> x >> y >> z >> a >> b >> c >> n;

        Matrix initialState(3, 3);
        initialState.mat[0][0] = x;
        initialState.mat[1][0] = y;
        initialState.mat[2][0] = z;

        Matrix companion(3, 3);
        companion.mat[0][1] = 1;
        companion.mat[1][2] = 1;
        companion.mat[2][0] = c;
        companion.mat[2][1] = b;
        companion.mat[2][2] = a;

        // hehe compton - daca citesti asta si nu intelegi referinta, ghinion. poti sa dai dm sa intrebi. daca intelegi, salut petrutz cmf
        Matrix compToN(3, 3);
        compToN = logPow(companion, n - 2);

        Matrix ans(3, 3);
        ans = compToN * initialState;
        fout << ans.mat[2][0] << "\n";
    }
    return 0;
}