#include <iostream>
#include <fstream>
using namespace std;
int calcul(int x,int y,int z,int a, int b,int c,int n)
{
	unsigned long long m[3][3], t[3];
	int i, j;
	for (i = 0; i < 3; i++)
	{
		for (j = 0; j < 3; j++)
		{
			m[i][j] = 0;
		}
	}
	m[0][0] = x;
	m[1][1] = y;
	m[2][2] = z;
	for (i = 3; i <= n; i++)
	{
		m[0][0] = c*m[0][0] + c*m[1][0] + c*m[2][0];
		m[0][1] = b*m[0][1] + b*m[1][1] + b*m[2][1];
		m[0][2] = a*m[0][2] + a*m[1][2] + a*m[2][2];
		memcpy(t, m[0], sizeof(t));
		memcpy(m[0], m[1], sizeof(t));
		memcpy(m[1], m[2], sizeof(t));
		memcpy(m[2], t, sizeof(t));
	}
	return m[2][0] + m[2][1] + m[2][2] % 666013;
}
int main()
{
	ifstream in("iepuri.in");
	ofstream out("iepuri.out");
	int n, m, i, x, y, z, a, b, c;
	in >> m;
	for (i = 1; i <= m; i++)
	{
		in >> x >> y >> z >> a >> b >> c >> n;
		out<<calcul(x, y, z, a, b, c,n)<<"\n";
	}
}