// http://infoarena.ro/problema/iepuri
#include <stdio.h>
#define mod 666013
int T;
long long N;

//rezultatul produsului a doua matrici
void produs(long long A[3][3], long long B[3][3], long long SOL[3][3])
{
 for (int i = 0; i < 3; i++)
	for (int j = 0; j < 3; j++)
		{
		 SOL[i][j] = 0;
		 for (int k = 0; k < 3; k++)
		     SOL[i][j] += A[i][k] * B[k][j];
		 SOL[i][j] %= mod;
		}
}

//M la puterea n
void putere(long long M[3][3], long long n, long long SOL[3][3])
{
 long long Aux[3][3];
 if (n == 1)
    {
      for (int i = 0 ; i < 3; i++)
	for (int j = 0; j < 3; j++)
		SOL[i][j] = M[i][j];
      return;
    }
 if (!(n % 2))
    {
     putere(M, n / 2, Aux);
     produs(Aux, Aux, SOL);
     return;
    }
 else
    {
     putere(M, n - 1, Aux);
     produs(Aux, M, SOL);
     return;
    }
}

int main()
{
 long long M[3][3], SOL[3][3], A[3][3], B[3][3];
 int i, j;
 M[0][0] = M[0][2] = 0;
 M[1][0] = M[1][1] = 0;
 M[0][1] = M[1][2] = 1;
 freopen("iepuri.in", "r", stdin);
 freopen("iepuri.out", "w", stdout);
 scanf("%d", &T);
 for (i = 0; i < 3; i++)
	for (j = 0; j < 3; j++)
		A[i][j] = B[i][j] = 0;
 for (i = 0; i < T; i++)
	{
	scanf("%lld %lld %lld %lld %lld %lld %lld", &A[0][0], &A[1][0],
	&A[2][0], &M[2][2], &M[2][1], &M[2][0], &N);
	M[2][0] %= mod;
	M[2][1] %= mod;
	M[2][2] %= mod;
	putere(M, N, SOL);
	produs(SOL, A, B);
	printf("%lld\n", B[0][0]);
	}
 return 0;
}