#include "pch.h"
#include <fstream>
//#include <iostream>

using namespace std;

ifstream cin("iepuri.in");
ofstream cout("iepuri.out");

static const int MOD = 666013;

void getMatrix(long long a[4][4], long long b[4][4])
{
	long long aux[4][4];
	for (int i = 0; i <= 3; ++i) {
		for (int j = 0; j <= 3; ++j) {
			aux[i][j] = 0;
		}
	}

	for (int i = 1; i <= 3; ++i) {
		for (int j = 1; j <= 3; ++j) {
			for (int k = 1; k <= 3; ++k) {
				aux[i][j] = (aux[i][j] + 1LL*(a[i][k] * b[k][j]) % MOD) % MOD;
			}
		}
	}

	for (int i = 1; i <= 3; ++i) {
		for (int j = 1; j <= 3; ++j) {
			a[i][j] = aux[i][j];
		}
	}
}

int solve()
{
	long long ans[4][4];
	long long base[4][4];

	for (int i = 1; i <= 3; ++i) {
		for (int j = 1; j <= 3; ++j) {
			ans[i][j] = 0;
			base[i][j] = 0;
		}
	}

	cin >> ans[1][1] >> ans[1][2] >> ans[1][3];
	cin >> base[3][3] >> base[2][3] >> base[1][3];

	base[2][1] = base[3][2] = 1;

	int exp;
	cin >> exp;

	while (exp) {
		if (exp % 2) {
			getMatrix(ans, base);
			exp--;
		}
		else {
			getMatrix(base, base);
			exp /= 2;
		}
	}

	return ans[1][1];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int t;
	cin >> t;
	while (t--) {
		cout << solve() << '\n';
	}
}