#include<stdio.h>

long long n,a[4][4], t, rez, b[4][4], nr, c[4][4], q, r, mod = 666013;

void ridic(long long ex)
{
	long long i, j, k;
	rez = 0;
	while (ex)
	{
		if (ex%2==0)
		{
			for (i=1; i<=3; i++)
				for (j=1; j<=3; j++)
					for(k=1; k<=3; k++)
						c[i][j] = ((c[i][j]%mod) + ((a[i][k]%mod)*(a[k][j]%mod))%mod)%mod;
			for (i=1; i<=3; i++)
				for (j=1; j<=3; j++) a[i][j]=c[i][j];
			ex/=2;
		}
		else {
			for (i=1; i<=3; i++)
				for (j=1; j<=3; j++)
					for(k=1; k<=3; k++)
						c[i][j] = ((c[i][j]%mod) + ((a[i][k]%mod)*(b[k][j]%mod))%mod)%mod;
			for (i=1; i<=3; i++)
				for (j=1; j<=3; j++) b[i][j]=c[i][j];
			ex--;
		     }
		for (int i=1; i<=3; i++)
			for (int j=1; j<=3; j++) c[i][j]=0;
	}

}




int main()
{
	freopen("iepuri.in","r",stdin);
	freopen("iepuri.out","w",stdout);
	scanf("%lld",&t);
	long long x, y, z, A, B, C, i, j, k;
	while (t--)
	{
		scanf("%lld %lld %lld %lld %lld %lld %lld", &x, &y, &z, &A, &B, &C, &n);
		a[1][1] = 0;		a[1][2] = 1;		a[1][3] = 0;
		a[2][1] = 0;		a[2][2] = 0;		a[2][3] = 1;
		a[3][1] = C;		a[3][2] = B;		a[3][3] = A;
		
		for (i=1; i<=3; i++)
			for (j=1; j<=3; j++) b[i][j]=a[i][j], c[i][j] = 0;
		ridic(n-1);

		a[1][1] = x;		a[1][2] = 0;		a[1][3] = 0;
		a[2][1] = y;		a[2][2] = 0;		a[2][3] = 0;
		a[3][1] = z;		a[3][2] = 0;		a[3][3] = 0;

		for ( i=1; i<=3; i++)
			for (j=1; j<=3; j++) c[i][j]=0;

		for (i=1; i<=3; i++)
				for (j=1; j<=3; j++)
					for(k=1; k<=3; k++)
						c[i][j] = ((c[i][j]%mod) + ((b[i][k]%mod)*(a[k][j]%mod))%mod)%mod;
		
		printf("%lld\n",c[1][1]);
	}
	return 0;
}