#include <stdio.h>
#include <string.h>
#define N 3
#define MOD 666013
#define lint long long int

struct vector 
{
	vector()
	{
		memset(data,0,sizeof(data));
	}
	lint data[N];
};

struct matrix
{
	matrix()
	{
		memset(data,0,sizeof(data));
	}
	lint data[N][N];
	matrix operator* (matrix& rhs)
	{
		matrix res;
		for (int i = 0; i < N; ++i)
			for (int j = 0 ; j < N ; ++j)
				for (int k = 0 ; k < N ; ++k)
				{
					res.data[i][j] += (data[i][k] * rhs.data[k][j]) % MOD;
					res.data[i][j] %= MOD;
				}

		return res;
				
	}
	vector operator* (vector& rhs)
	{
		vector rez;
		for (int i = 0 ; i < N ; ++i)
			for (int j = 0 ; j < N ; ++j)
			{
				rez.data[i] += (rhs.data[j] * data[i][j]) % MOD;
				rez.data[i] %= MOD;
			}

		return rez;
	}
};

matrix identity()
{
	matrix res;
	for (int i = 0 ; i < N; ++i)
		res.data[i][i] = 1;
	return res;
}

matrix fastexp(matrix b,int e)
{
	if ( e == 0)
		return identity();
	if ( e == 1)
		return b;

	matrix temp = fastexp(b,e/2);
	temp = temp * temp;

	if ( e % 2 == 0)
		return temp;

	return temp * b;
}

int main()
{
	freopen("iepuri.in","r",stdin);
	freopen("iepuri.out","w",stdout);


	int t;
	scanf("%d",&t);

	while (t--)
	{
		matrix m;
		vector v;
		int n;

		m.data[0][1] = 1;
		m.data[1][2] = 1;

		scanf("%d%d%d%d%d%d%d",&v.data[0],&v.data[1],&v.data[2],&m.data[2][2],&m.data[2][1],&m.data[2][0],&n);

		m = fastexp(m,n);
		v = m * v;

		printf("%d\n",v.data[0]);
	}

}