#include <fstream>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
using namespace std;

ifstream fi ("iepuri.in");
ofstream fo ("iepuri.out");

const int dim = 5, mod = 666013;
int N, T, M[dim][dim], C[dim][dim], P[dim][dim], X[dim][dim];

void cit ()
{
	int i, j;
	fi >> X[3][1] >> X[2][1] >> X[1][1] >> M[1][1] >> M[1][2] >> M[1][3] >> N;
	for (i = 1; i <= 3; i++)
	{
		for (j = 1; j <= 3; j++)
		{
			P[i][j] = 0;
		}
		P[i][i] = 1;
	}
}		

void mul (int *R, int *A, int *B, int m, int n, int p)
{
	int i, j, k;
	for (i = 1; i <= m; i++)
		for (j = 1; j <= p; j++)
		{
			C[i][j] = 0;
			for (k = 1; k <= n; k++)
				C[i][j] += ((long long)*(A+dim*i+k) * *(B+dim*k+j)) % mod;
		}
	for (i = 1; i <= m; i++)
		for (j = 1; j <= p; j++)
			*(R+dim*i+j) = C[i][j];
}

void exp (int n)
{
	for (int b = 31; b >= 0; b--)
	{
		mul ((int*)P, (int*)P, (int*)P, 3, 3, 3);
		if ((n >> b) & 1)
			mul ((int*)P, (int*)P, (int*)M, 3, 3, 3);
	}
}

void afi ()
{
	mul ((int*)P, (int*)P, (int*)X, 3, 3, 1);
	fo << P[1][1] << '\n';
}

int main ()
{
	M[2][1] = M[3][2] = 1;
	fi >> T;
	while (T--)
	{
		cit ();
		exp (N - 2); 
		afi ();
	}
	
	return 0;
}