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

const int MOD = 666013;
const int KMAX = 3;

void multiply_matrix(int A[KMAX][KMAX], int B[KMAX][KMAX], int C[KMAX][KMAX]) {
    int tmp[KMAX][KMAX];

    // tmp = A * B
    for (int i = 0; i < KMAX; ++i) {
        for (int j = 0; j < KMAX; ++j) {
            unsigned long long sum = 0; // presupun ca o suma intermediara incape pe 64 de biti

            for (int k = 0; k < KMAX; ++k) {
                sum += (1LL * A[i][k] * B[k][j]) % MOD;
				sum = sum % MOD;
            }

            tmp[i][j] = sum;
        }
    }

    //  C = tmp
    memcpy(C, tmp, sizeof(tmp));
}

// R = C^p
void power_matrix(int C[KMAX][KMAX], int p, int R[KMAX][KMAX]) {
    // tmp = I
    int tmp[KMAX][KMAX];
    for (int i = 0; i < KMAX; ++i) {
        for (int j = 0; j < KMAX; ++j) {
            tmp[i][j] = (i == j) ? 1 : 0;
        }
    }

    while (p != 1) {
        if  (p % 2 == 0) {
            multiply_matrix(C, C, C); // C = C*C
            p /= 2;                   // ramane de calculat C^(p/2)
        } else {
            // reduc la cazul anterior:
            multiply_matrix(tmp, C, tmp); // tmp = tmp*C
            --p;                          // ramane de calculat C^(p-1)
        }
    }

    // avem o parte din rezultat in C si o parte in tmp
    multiply_matrix(C, tmp, R); // rezultat = tmp * C
}


class Task {
 public:
	void solve() {
		read_input();
		print_output(get_result());
	}

 private:
	int t, x, y, z, a, b, c, n;
	vector<int> xs, ys, zs, as, bs, cs, ns;

	void read_input() {
		ifstream fin("iepuri.in");
		fin >> t;

		for (int i = 0; i < t; i++) {
			fin >> x >> y >> z >> a >> b >> c >> n;
			xs.push_back(x);
			ys.push_back(y);
			zs.push_back(z);
			as.push_back(a);
			bs.push_back(b);
			cs.push_back(c);
			ns.push_back(n);
		}
		fin.close();
	}

	vector<int> get_result() {
		
		vector<int> results;

		for (int i = 0; i < t; i++) {
			int C[KMAX][KMAX] = {{0, 0, cs[i]}, 
                                 {1, 0, bs[i]}, 
                                 {0, 1, as[i]}};
			power_matrix(C, ns[i] - 2, C);
			results.push_back((xs[i] * C[0][2] % MOD + ys[i] * C[1][2] % MOD + zs[i] * C[2][2] % MOD) % MOD); 			
		}
		
		return results;
	}

	void print_output(vector<int> results) {
		ofstream fout("iepuri.out");
		for (int i = 0; i < t; i++)
			fout << results[i] << "\n";
		fout.close();
	}
};

int main() {
	Task task;
	task.solve();
	return 0;
}