#include<iostream>
#include<fstream>

using namespace std;

const int MOD = 666013;
const int MDIM = 5;
int dp[MDIM][MDIM];

void multiplication(int a[MDIM][MDIM], int b[MDIM][MDIM], int l1, int l2, int l3) {
	int result[MDIM][MDIM];
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			result[i][j] = 0;
		}
	}

	for (int k = 0; k < l2; k++) {
		for (int i = 0; i < l1; i++) {
			for (int j = 0; j < l3; j++) {
				result[i][j] = (result[i][j] + a[i][k]*b[k][j]) % MOD;
			}
		}	
	}		
	
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			a[i][j] = result[i][j];
		}
	}
}

void matrixPow(int dp[MDIM][MDIM], int n) {
	int aux[MDIM][MDIM];

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

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

	while (n > 0) {
		if (n % 2 == 1) {
			multiplication(dp, aux, 3, 3, 3);
		}
		n = n/2;
		multiplication(aux, aux, 3, 3, 3);
	}
}

int main() {
	ifstream f("iepuri.in");
	ofstream g("iepuri.out");
	int t, n, a, b, c, x, y, z;

	f >> t;
	for (int i = 1; i <= t; i++) {
		f >> x >> y >> z >> a >> b >> c >> n;
		
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				dp[i][j] = 0;
			}
		}
		dp[1][0] = 1;
		dp[2][1] = 1;
		dp[0][2] = c;
		dp[1][2] = b;
		dp[2][2] = a;
		matrixPow(dp, n-2);

		int result = (x * dp[0][2] + y * dp[1][2] + z * dp[2][2]) % MOD;
		g << result << '\n';
	}

	return 0;
}