#include <bits/stdc++.h>
using namespace std;

void multiply(int m[3][3], int a[3][3])
{
	long long c[3][3] = {0};
	for(int i = 0; i < 3; ++i)
		for(int j = 0; j < 3; ++j){
			for(int k = 0; k < 3; ++k)
				c[i][j] += 1LL * a[i][k] * m[k][j];
			c[i][j] %= 666013;
		}
	for(int i = 0; i < 3; ++i)
		for(int j = 0; j < 3; ++j)
			a[i][j] = c[i][j];
}

int main()
{
	(void)! freopen("iepuri.in", "r", stdin);
	(void)! freopen("iepuri.out", "w", stdout);
	cin.tie(0); ios_base::sync_with_stdio(false);
	int a, b, c, t, x, y, z, n;
	cin >> t;
	while(t--)
	{
		int m[3][3]={0}, s[3][3]={0};
		cin >> x >> y >> z >> a >> b >> c >> n;
		m[0][2] = c;
		m[1][2] = b;
		m[2][2] = a;
		m[1][0] = m[2][1] = 1;
		s[0][0] = x;
		s[0][1] = y;
		s[0][2] = z;

		while(n)
		{
			if(n%2==1) multiply(m, s);
			multiply(m, m);
			n/=2;
		}
		cout << s[0][0] << '\n';
	}
	return 0;
}