#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;
const int MOD = 666013;

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

class Matrix {
public:
    vector<vector<int>> mat;
    int n;

    Matrix(int size, bool flag = false) : n(size) {
        mat.assign(n, vi(n, 0));
        if (flag) {
            for (int i = 0; i < n; i++)
                mat[i][i] = 1;
        }
    }
    Matrix operator*(const Matrix &other) const {
        Matrix result(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    result.mat[i][j] = (result.mat[i][j] + 1LL * mat[i][k] * other.mat[k][j]) % MOD;
                }
            }
        }
        return result;
    }

    Matrix& operator*=(const Matrix &other) {
        *this = *this * other;
        return *this;
    }

    Matrix pow(long long exp) const {
        Matrix result(n, true), base = *this;
        while (exp) {
            if (exp & 1)
                result = result * base;
            base *= base;
            exp >>= 1;
        }
        return result;
    }
};
int n;
void solve_testcase() {
    int x, y, z, a, b, c, n;
    fin >> x >> y >> z >> a >> b >> c >> n;
    Matrix M(3);
    M.mat = {
        {a, b, c},
        {1, 0, 0},
        {0, 1, 0}
    };
    M = M.pow(n - 2);
    fout << (z * M.mat[0][0] + y * M.mat[0][1] + x * M.mat[0][2]) % MOD << "\n";
}
signed main() {
    int t;
    fin >> t;
    while (t--)
        solve_testcase();
    return 0;
}