#include <fstream>
#define M 666013
using namespace std;
ifstream f("iepuri.in");
ofstream g("iepuri.out");
class Matrix_3X3
{
public:
	long long matrix[3][3];
	void Create(int a, int b, int c, int d, int e, int f, int g, int h, int i)
	{
		matrix[0][0] = a, matrix[0][1] = b, matrix[0][2] = c;
		matrix[1][0] = d, matrix[1][1] = e, matrix[1][2] = f;
		matrix[2][0] = g, matrix[2][1] = h, matrix[2][2] = i;
	}

	void Copy(long long A[3][3])
	{
		for (int i = 0; i < 3; i++)
		{
			for (int j = 0; j < 3; j++)
			{
				matrix[i][j] = A[i][j];
			}
		}
	}

	void Product(Matrix_3X3 A)
	{
		Matrix_3X3 temp;
		temp.Copy(matrix);
		for (int i = 0; i < 3; i++)
		{
			for (int j = 0; j < 3; j++)
			{
				matrix[i][j] = (temp.matrix[i][0] * A.matrix[0][j] % M + temp.matrix[i][1] * A.matrix[1][j] % M + temp.matrix[i][2] * A.matrix[2][j] % M) % M;
			}
		}
	}
};

void Small_test(int d1, int d2, int d3, int d4, int d5, int n)
{
	switch (n)
	{
	case 1:
		g << d1 << '\n';
		return;
	case 2:
		g << d2 << '\n';
		return;
	case 3:
		g << d3 << '\n';
		return;
	case 4:
		g << d4 << '\n';
		return;
	default:
		g << d5 << '\n';
	}
}

void Fast_exp(Matrix_3X3& iepuri, Matrix_3X3 tribo, int n)
{
	while (n)
	{
		if (n % 2 == 1)
		{
			iepuri.Product(tribo);
		}
		tribo.Product(tribo);
		n = n / 2;
	}
}

int T,i,x,y,z,a,b,c,t,l,n;
Matrix_3X3 iepuri, tribo;
int main()
{
	f >> T;
	for (i = 1; i <= T; i++)
	{
		f >> z >> y >> x >> a >> b >> c >> n;
		n++;
		t = (x * a + y * b + z * c) % M;
		l = (t * a + x * b + y * c) % M;
		if (n <= 5)
		{
			Small_test(x, y, z, t, l, n);
			continue;
		}
		iepuri.Create(l, t, x, t, x, y, x, y, z);
		tribo.Create(a, 1, 0, b, 0, 1, c, 0, 0);
		Fast_exp(iepuri, tribo, n - 5);
		g << iepuri.matrix[0][0] << '\n';
	}
	return 0;
}