#include <iostream>
#include <fstream>

#define int long long

using namespace std;

ifstream fin("iepuri.in");
ofstream fout("iepuri.out");

/* fast matrix exponantionation tools: */

const int N = 10, mod = 666013;

int aux[N + 1][N + 1];
void mult(int mat1[N + 1][N + 1], int mat2[N + 1][N + 1], int prod[N + 1][N + 1], int n, int m, int p){

	for(int i = 1; i <= m; i++)
		for(int j = 1; j <= m; j++)
			aux[i][j] = 0;

	for(int i = 1; i <= m; i++)
		for(int j = 1; j <= m; j++)
			for(int k = 1; k <= m; k++)
				(aux[i][j] += mat1[i][k] * mat2[k][j]) %= mod;

	for(int i = 1; i <= m; i++)
		for(int j = 1; j <= m; j++)
			prod[i][j] = aux[i][j];
}	

int rez[N + 1][N + 1];
void exp(int m[N + 1][N + 1], int n, int exp){

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			rez[i][j] = 0;

	for(int i = 1; i <= n; i++)
		rez[i][i] = 1;

	while(exp != 0){
		if(exp % 2 != 0)
			mult(rez, m, rez, n, n, n);

		mult(m, m, m, n, n, n);

		exp /= 2;
	}

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			m[i][j] = rez[i][j];
}

/*----------------------------------------------*/

void solve(){
	int x, y, z, a, b, c, n;
	fin >> x >> y >> z >> a >> b >> c >> n;

	int trans[N + 1][N + 1];
	trans[1][1] = 0, trans[2][1] = 1, trans[3][1] = 0;
	trans[1][2] = 0, trans[2][2] = 0, trans[3][2] = 1;
	trans[1][3] = c, trans[2][3] = b, trans[3][3] = a;

	exp(trans, 3, n - 2);

	int ans[N + 1][N + 1];
	ans[1][1] = x, ans[1][2] = y, ans[1][3] = z;

	mult(ans, trans, ans, 1, 3, 3);

	fout << ans[1][3] << '\n';
}

signed main(){

	int T;
	fin >> T;

	while(T--)
		solve();

	return 0;
}