#include <stdio.h>
int main()
{
	freopen("iepuri.in","r",stdin);
	freopen("iepuri.out","w",stdout);
	int x,y,z,a,b,c,n,t,i,j,sch;
	scanf("%d",&t);
	for (i=1; i<=t; i++)
	{
		scanf("%d%d%d%d%d%d%d",&x,&y,&z,&a,&b,&c,&n);
		while (n-2)
		{
			sch=z;
			z=z*a%666013;
			z+=y*b%666013;
			z+=x*c%666013;
			x=y;
			y=sch;
			n--;
		}
		printf("%d\n",z%666013);
	}
	return 0;
}