#include<fstream>

int main()
{
	std::ifstream f("iepuri.in");
	std::ofstream g("iepuri.out");
	long t, x, y, z, a, b, c, n;
	f >> t;
	long x1;
	for (long i = 0; i < t; i++)
	{
		f >> x >> y >> z >> a >> b >> c >> n;
		for (long i = 3; i <= n; i++)
		{
			x1 = x;
			x = y;
			y = z;
			z = (y*a + x*b + x1*c);
			if (z >= 666013) z ^= 666013;
		}
		g << z << std::endl;
	}
	f.close();
	g.close();
	return 0;
}