#include <fstream>
#include <string>
#include <string.h>

using namespace std;

#define MODULO 666013

class Matrix3 {
	public:

	Matrix3() {
		memset( & data, 0, sizeof(data));
	}

	Matrix3(int init[3], bool type) {
		memset( & data, 0, sizeof(data));
		if (type == true) {
			for (int i = 0; i < 3; i++) {
				data[0][i] = init[i];
			}
		} else {
			for (int i = 0; i < 3; i++) {
				data[i][2] = init[i];
			}
			data[1][0] = 1;
			data[2][1] = 1;
		}
	}

	long long * operator[](int i) {
		return &data[i][0];
	}

	Matrix3 power(int power) {
		Matrix3 current = * this;
		Matrix3 result;
		for (int i = 0; i < 3; i++) {
			result[i][i] = 1;
		}

		for (int i = 0; i <= 31; i++) {

			if ((1 << i) & power) {
				result = result * current;
			}
			current = current * current;
		}
		return result;
	}

	Matrix3 operator * (Matrix3 & other) {
		Matrix3 result;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				for (int z = 0; z < 3; z++) {
					result[i][j] += (this - > data[i][z] * other.data[z][j]) % MODULO;
					result[i][j] %= MODULO;
				}
			}
		}

		return result;
	}

	protected:

	private: long long data[3][3];

};

inline void readVector(int vector[3], istream & stream) {
	for (int i = 0; i < 3; i++) {
		stream >> vector[i];
	}
}

inline void readVectorReverse(int vector[3], istream & stream) {
	for (int i = 2; i >= 0; i--) {
		stream >> vector[i];
	}
}

void solve() {
	ifstream in("iepuri.in");
	ofstream out("iepuri.out");

	int questionCount;

	in >> questionCount;

	for (int i = 0; i < questionCount; i++) {

		int xyz[3];
		int abc[3];
		int n;

		readVector(xyz, in);
		readVectorReverse(abc, in);

		in >> n;

		Matrix3 matrixXYZ(xyz, true);
		Matrix3 matrixABC(abc, false);

		matrixABC = matrixABC.power(n - 2);
		matrixXYZ = matrixXYZ * matrixABC;
		out << matrixXYZ[0][2] << "\n";

	}
}

int main() {
	solve();
	return 0;
}