#include <iostream>
#include <vector>

using namespace std;

typedef vector<vector<long long>> Matrix;
const int MOD = 666013;

Matrix mul(const Matrix& A, const Matrix& B) {
    int rows_A = A.size();
    int cols_A = A[0].size();
    int cols_B = B[0].size();
    Matrix C(rows_A, vector<long long>(cols_B, 0));
    for (int i = 0; i < rows_A; i++) {
        for (int k = 0; k < cols_A; k++) {
            if (A[i][k] == 0) continue;
            for (int j = 0; j < cols_B; j++) {
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
            }
        }
    }
    return C;
}

Matrix pow_iterative(Matrix A, long long p) {
    Matrix res(3, vector<long long>(3, 0));
    res[0][0] = res[1][1] = res[2][2] = 1;
    while (p > 0) {
        if (p % 2 == 1) res = mul(res, A);
        A = mul(A, A);
        p /= 2;
    }
    return res;
}

long long helper(long long x, long long y, long long z, long long a, long long b, long long c, long long n) {
    if (n == 0) return x % MOD;
    if (n == 1) return y % MOD;
    if (n == 2) return z % MOD;

    Matrix C(3, vector<long long>(3, 0));
    C[1][0] = 1;
    C[2][1] = 1;
    C[0][2] = c % MOD;
    C[1][2] = b % MOD;
    C[2][2] = a % MOD;

    Matrix C_n = pow_iterative(C, n - 2);
    
    long long res = (x % MOD * C_n[0][2]) % MOD;
    res = (res + (y % MOD * C_n[1][2]) % MOD) % MOD;
    res = (res + (z % MOD * C_n[2][2]) % MOD) % MOD;

    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        long long x, y, z, a, b, c, n;
        cin >> x >> y >> z >> a >> b >> c >> n;
        cout << helper(x, y, z, a, b, c, n) << "\n";
    }
    return 0;
}