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