#include <fstream>

using namespace std;

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

struct ModInt {
	static void setMod(int mod) {
		kMod = mod;
	}

	ModInt(int x = 0) { x_ = x % kMod; }
	ModInt(long long x) { x_ = x % kMod; }

	ModInt operator+(const ModInt& rhs) const {
		return ModInt(x_ + rhs.x_);
	}
	ModInt operator-(const ModInt& rhs) const {
		return ModInt(x_ - rhs.x_);
	}
	ModInt operator*(const ModInt& rhs) const {
		return ModInt(1LL * x_ * rhs.x_);
	}
	ModInt operator/(const ModInt& rhs) const {
		return (*this) * (rhs ^ (kMod - 2));
	}
	ModInt operator^(const int p) const {
		if (p == 0) {
			return ModInt(1);
		} else if (p % 2) {
			ModInt result = ((*this) ^ (p / 2));
			return result * result;
		} else {
			return (*this) * ((*this) ^ (p - 1));
		}
	}

	ModInt& operator+=(const ModInt& rhs) {
		(*this) = (*this) + rhs;
		return (*this);
	}
	ModInt& operator-=(const ModInt& rhs) {
		(*this) = (*this) - rhs;
		return (*this);
	}
	ModInt& operator*=(const ModInt& rhs) {
		(*this) = (*this) * rhs;
		return (*this);
	}
	ModInt& operator/=(const ModInt& rhs) {
		(*this) = (*this) / rhs;
		return (*this);
	}
	ModInt& operator^=(const int p) {
		(*this) = ((*this) ^ p);
		return (*this);
	}

	operator int() {
		return (x_ + kMod) % kMod;
	}

private:
	int x_;
	static int kMod;
};

int ModInt::kMod = 0;

template<class type>
struct Matrice {
	static void setSize(int n) {
		sz = n;
	}

	Matrice(type diag = 0) {
		a.resize(sz, vector<type>(sz));
		for (int i = 0; i < sz; i++) {
			a[i][i] = diag;
		}
	}

	vector<type>& operator[](int i) {
		return a[i];
	}

	const vector<type>& operator[](int i) const {
		return a[i];
	}

	Matrice operator+(const Matrice& other) const {
		Matrice result;
		for (int i = 0; i < sz; i++) {
			for (int j = 0; j < sz; j++) {
				result[i][j] = a[i][j] + other[i][j];
			}
		}
		return result;
	}

	Matrice operator*(const Matrice& other) const {
		Matrice result;
		for (int i = 0; i < sz; i++) {
			for (int j = 0; j < sz; j++) {
				for (int k = 0; k < sz; k++) {
					result[i][j] += a[i][k] * other[k][j];
				}
			}
		}
		return result;
	}

	Matrice operator^(const int p) const {
		Matrice result = Matrice(1);
		if (p == 0) {
			return result;
		} else if (p % 2 == 0) {
			result = (*this) ^ (p / 2);
			return result * result;
		} else {
			return (*this) * ((*this) ^ (p - 1));
		}
	}

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

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

	Matrice& operator^=(const int p) {
		(*this) = ((*this) ^ p);
		return (*this);
	}

private:
	static int sz;
	vector<vector<type>> a;
};

template<class type>
int Matrice<type>::sz = 0;

void solveTest() {
	/*
	t0 = x, t1 = y, t2 = z
	ti = a * t(i - 1) + b * t(i - 2) + c * t(i - 3)

	T2 = 0 0 z
		 0 0 y
		 0 0 x

	A = a b c
		1 0 0
		0 1 0

	T2 * A ^ (n - 2) = Tn

	Tn = 0 0 tn
		 0 0 tn-1
		 0 0 tn-2
	*/

	int x, y, z; cin >> x >> y >> z;
	int a, b, c; cin >> a >> b >> c;
	int n; cin >> n;

	Matrice<ModInt> T2; 
	T2[0][2] = z; T2[1][2] = y; T2[2][2] = x;

	Matrice<ModInt> A;
	A[0][0] = a; A[0][1] = b; A[0][2] = c;
	A[1][0] = A[2][1] = 1;

	// cerr << A[0][0] << " " << A[0][1] << " " << A[0][2] << endl;

	A ^= (n - 2);

	// cerr << A[0][0] << " " << A[0][1] << " " << A[0][2] << endl;
	// cerr << T2[0][2] << " " << T2[1][2] << " " << T2[2][2] << endl;

	Matrice<ModInt> Tn = A * T2;
	cout << int(Tn[0][2]) << "\n";
}

int main() {
	ModInt::setMod(666013);
	Matrice<ModInt>::setSize(3);

	int t; cin >> t;
	for (int i = 0; i < t; i++) {
		solveTest();
	}
}