#include<stdio.h>

int a,b,c,x,y,z,n;
long s;


int main()
{
	int t;
	FILE *f=fopen("iepuri.in","r");
        FILE *g=fopen("iepuri.out","w");
	fscanf(f,"%i",&t);
	for(int i=1;i<t;++i)
		{
		fscanf(f,"%i %i %i %i %i %i %ld",&x,&y,&z,&a,&b,&c,&n);
		s=0;
		for(long j=3;j<=n;++j)
			{
			if (s>666013)
				s-=666013;
			s=a*z+b*y+c*x;
			x=y;
			y=z;
			z=s;
			}
		fprintf(g,"%ld\n",s);
		}
	fscanf(f,"%i %i %i %i %i %i %ld",&x,&y,&z,&a,&b,&c,&n);
	s=0;
	for(long j=3;j<=n;++j)
		{
		if (s>666013)
			s-=666013;
		s=a*z+b*y+c*x;
		x=y;
		y=z;
		z=s;
		}
	fprintf(g,"%ld",s);
	return 0;
}