#include <bits/stdc++.h>
using namespace std;

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

#define MOD 666013

void multiply_matrix(int a[3][3], int b[3][3], int c[3][3]) {
    int tmp[3][3] = {0};
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            unsigned long long sum = 0;
            for (int k = 0; k < 3; ++k) {
                sum += (1LL * a[i][k] * b[k][j]) % MOD;
            }
            tmp[i][j] = sum % MOD;
        }
    }
    memcpy(c, tmp, sizeof(tmp));
}

void exp_matrix(int x[3][3], int exp, int res[3][3]) {
    int tmp[3][3];
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            tmp[i][j] = (i == j) ? 1 : 0;
        }
    }
    while (exp > 0) {
        if (exp % 2 == 1) {
            multiply_matrix(tmp, x, tmp);
        }
        multiply_matrix(x, x, x);
        exp /= 2;
    }
    memcpy(res, tmp, sizeof(tmp));
}

int main() {
    int x, y, z, a, b, c, n, t;
    fin >> t;
    int mat[3][3], res[3][3];
    for (int i = 1; i <= t; i++) {
        fin >> x >> y >> z >> a >> b >> c >> n;
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                mat[j][k] = 0;
                res[j][k] = 0;
            }
        }
        mat[1][0] = 1;
        mat[2][1] = 1;
        mat[0][2] = c;
        mat[1][2] = b;
        mat[2][2] = a;
        if (n == 1) {
            fout << x % MOD << '\n';
            continue;
        } else if (n == 2) {
            fout << y % MOD << '\n';
            continue;
        }
        exp_matrix(mat, n-2, res);
        fout << (x * res[0][2] + y * res[1][2] + z * res[2][2]) % MOD << '\n';
    }
    return 0;
}