#include <stdio.h>
#define m 666013

FILE *f=fopen("iepuri.in","r");
FILE *g=fopen("iepuri.out","w");

int main()
{
	int a,b,c,x,y,z,n,i,j,s,t,k,l;
	fscanf(f,"%d",&t);
	for(i=1;i<=t;i++)
	{
		int r[10000][3];
		fscanf(f,"%d%d%d%d%d%d%d",&x,&y,&z,&a,&b,&c,&n);
		r[1][1]=z;
		r[1][2]=y;
		r[1][3]=x;
		s=r[1][1]*a+r[1][2]*b+r[1][3]*c;
		l=s;
		for(j=2;j<=n-2;j++)
		{
			s=0;
			for(k=1;k<=3;k++)
			{
				if(k==1)
				{
					r[j][k]=l;
					s=s+r[j][k]*a;
				}
				else
					if(k==2)
					{
						r[j][k]=r[j-1][k-1];
						s=s+r[j][k]*b;
					}
					else
					{
						r[j][k]=r[j-1][k-1];
						s=s+r[j][k]*c;
					}
			l=s;
			}
		}
		fprintf(g,"%d\n",l%m);
	}
}