// http://infoarena.ro/problema/iepuri
#include <stdio.h>
#define Nmax 4
int A, B, C, T;
long long F[Nmax];
long long N;

int main()
{
 freopen("iepuri.in", "r", stdin);
 freopen("iepuri.out", "w", stdout);
 scanf("%d", &T);
 for (int j = 0; j < T; j++)
	{
	scanf("%ld %ld %ld %d %d %d %ld", &F[0], &F[1], &F[2], &A, &B, &C, &N);
	for (int i = 3; i <= N; i++)
	       {
		F[3] = C * F[0] + B * F[1] + A * F[2];
		F[0] = F[1];
		F[1] = F[2];
		F[2] = F[3];
	       }
	printf("%lld\n", F[3]%666013);
        }
 return 0;
}