#include <stdio.h>
int main()
{
	unsigned int x,c,y,b,z,a,n,i,t,j,e,f,g=666013;
	FILE *f1,*f2;
	f1=fopen("iepuri.in","r");
	f2=fopen("iepuri.out","w");
	fscanf(f1,"%d",&t);
	for(i=1;i<=t;i++)
	{
		fscanf(f1,"%d%d%d%d%d%d%d",&x,&y,&z,&a,&b,&c,&n);
		x=x%g;
		y=y%g;
		z=z%g;
		a=a%g;
		b=b%g;
		c=c%g;
		for(j=3;j<=n;j++)
		{
			e=z%g;
			z=(z*a+y*b+x*c)%g;
			x=y%g;
			y=e;
		}
		fprintf(f2,"%d\n",z%g);
	}
	fclose(f1);
	fclose(f2);
	return 0;
}