#include <assert.h>
#include <stdio.h>
#include <string.h>

/*
 * F*ckin' genius.
 */

enum { modulo = 666013, maxpow = 32 };

struct matrix
{
	int a[3][3];

	void make_identity()
	{
		memset(a, 0, sizeof(a));

		for(int i = 0; i < 3; i++)
			a[i][i] = 1;
	}

	void operator=(const matrix &m)
	{
		memcpy(a, m.a, sizeof(a));
	}

	void operator*=(const matrix &m)
	{
		int i, j, k;
		matrix tmp;

		//MBO
		for(i = 0; i < 3; i++)
			for(j = 0; j < 3; j++)
			{
				tmp.a[i][j] = 0;
				for(k = 0; k < 3; k++)
				{
					long long t = a[i][k];
					t *= m.a[k][j];
					t %= modulo;

					tmp.a[i][j] += t;
					tmp.a[i][j] %= modulo;
				}
			}

		/*
		printf("------------------------------------------\n");
		print();
		printf("*\n");
		m.print();
		printf("=\n");
		tmp.print();
		printf("------------------------------------------\n\n");
		*/

		operator=(tmp);
	}

	/*
	void print() const
	{
		int i, j;

		for(i = 0; i < 3; i++)
		{
			for(j = 0; j < 3; j++)
			{
				printf("%6d ", a[i][j]);
				assert(a[i][j] >= 0 && a[i][j] < modulo);
			}

			printf("\n");
		}
	}
	*/
			
} pow[maxpow], prod, initial, ans; //pow[0] == ^1 and so on
int wanted;

void calc_pow()
{
	for(int i = 1; i < maxpow; i++)
	{
		pow[i] = pow[i - 1];
		pow[i] *= pow[i - 1];
	}

	/*
	for(int i = 0; i < maxpow; i++)
	{
		printf("pow[%d]:\n", i);
		pow[i].print();
		printf("\n");
	}
	printf("\n");
	*/
}

void go()
{
	calc_pow();
	
	//rise pow[0]^wanted in O(logN)
	prod.make_identity();
	//printf("wanted %d\n", wanted);
	for(int i = 0; i < maxpow; i++)
		if(wanted & (1 << i))
		{
			//printf("using pow[%d]\n", i);

			prod *= pow[i];
		}

	/*
	printf("prod\n");
	prod.print();
	printf("initial\n");
	initial.print();
	printf("\n");
	*/

	ans = prod;
	ans *= initial;

	/*
	printf("ans\n");
	ans.print();
	*/
}

int main()
{
	int tests, i;
	FILE *f = fopen("iepuri.in", "r"),
	     *fo = fopen("iepuri.out", "w");
	if(!f || !fo) return 1;

	pow[0].a[0][1] = 1;
	pow[0].a[1][2] = 1;

	fscanf(f, "%d", &tests);
	for(i = 0; i < tests; i++)
	{
		fscanf(f, "%d%d%d%d%d%d%d", &initial.a[0][0], &initial.a[1][0], &initial.a[2][0],
				&pow[0].a[2][2], &pow[0].a[2][1], &pow[0].a[2][0],
				&wanted);
		wanted -= 2;

		go();

		fprintf(fo, "%d\n", ans.a[2][0]);

		//printf("---------------- end of test %d\n\n\n", i);
	}

	fclose(f);
	fclose(fo);
	return 0;
}