#include <iostream>
#include <fstream>
using namespace std;
ifstream in("iepuri.in");
ofstream out("iepuri.out");
void ridfact(unsigned long long m[3][3], int t)
{
	unsigned long long i, j, k, n[3][3], x[3][3], tot;
	if (t == 1) { return; }
	else
	{
		if (t % 2 == 1)
		{
			for (i = 0;i < 3;i++)
			{
				for (j = 0;j < 3;j++)
				{
					n[i][j] = m[i][j];
				}
			}
			for (i = 0;i <= 2;i++)
			{
				for (j = 2;j <= 2;j++)
				{
					m[i][j] %= 666013;
				}
			}
			ridfact(m, t - 1);
			for (i = 0;i <= 2;i++)
			{
				for (j = 0;j <= 2;j++)
				{
					tot = 0;
					for (k = 0;k <= 2;k++)
					{
						tot += m[i][k] * n[k][j];
						tot %= 666013;
					}
					x[i][j] = tot;
				}
			}
			for (i = 0;i < 3;i++)
			{
				for (j = 0;j < 3;j++)
				{
					m[i][j] = x[i][j];
				}
			}
		}
		else
		{
			for (i = 0;i < 3;i++)
			{
				for (j = 0;j < 3;j++)
				{
					n[i][j] = m[i][j];
				}
			}
			for (i = 0;i <= 2;i++)
			{
				for (j = 0;j <= 2;j++)
				{
					tot = 0;
					for (k = 0;k <= 2;k++)
					{
						tot += m[i][k] * n[k][j];
						tot %= 666013;
					}
					x[i][j] = tot;
				}
			}
			for (i = 0;i < 3;i++)
			{
				for (j = 0;j < 3;j++)
				{
					m[i][j] = x[i][j];
				}
			}
			for (i = 0;i <= 2;i++)
			{
				for (j = 2;j <= 2;j++)
				{
					m[i][j] %= 666013;
				}
			}
			ridfact(m, t / 2);
		}
	}
	for (i = 0;i <= 2;i++)
	{
		for (j = 2;j <= 2;j++)
		{
			m[i][j]%=666013;
		}
	}
}
void rez()
{
	int a, b, c, x, y, z,n;
	unsigned long long m[3][3] = { {0,1,0},{0,0,1},{0,0,0} };
	in >> x;
	in >> y;
	in >> z;
	in >> a;
	in >> b;
	in >> c;
	in >> n;
	m[2][0] = c;
	m[2][1] = b;
	m[2][2] = a;
	ridfact(m, n);
	out << 1LL*(m[0][0] * x%666013 + m[0][1] * y%666013 + m[0][2] * z%666013) % 666013<<"\n";
}
int main()
{
	
	int t,i,x;
	in >> t;
	for (i = 1;i <= t;i++)
	{
		rez();
	}
}