#include<stdio.h>
#include<limits.h>
#define NMAX	666013

int main()
{
struct test{unsigned long  x,y,z,a,b,c,n,max;};
struct coef{unsigned long  c1,c2,c3;};
coef c[4]={{1,0,0},{0,1,0},{0,0,1}};
coef c0={1,0,0},c1={0,1,0},c2={0,0,1};
test v[101];
unsigned long  t,i,j,aux,MAX;
freopen("iepuri.in","r",stdin);
freopen("iepuri.out","w",stdout);
scanf("%lu",&t);
for(i=1;i<=t;i++){
	scanf("%lu%ld%lu%lu%lu%lu%lu",
	&v[i].x,&v[i].y,&v[i].z,&v[i].a,&v[i].b,&v[i].c,&v[i].n);
	if(v[i].a>=v[i].b) v[i].max=v[i].a;
	else v[i].max=v[i].b;
	if(v[i].c>v[i].max) v[i].max=v[i].c;
	}

for(i=1;i<=t;i++)
	{
	MAX=ULONG_MAX/v[i].max;
	MAX=MAX/1000;
	for(j=3;j<=v[i].n;j++)
		{
		c[3].c1=c[2].c1*v[i].a+c[1].c1*v[i].b+c[0].c1*v[i].c;
		c[3].c2=c[2].c2*v[i].a+c[1].c2*v[i].b+c[0].c2*v[i].c;
		c[3].c3=c[2].c3*v[i].a+c[1].c3*v[i].b+c[0].c3*v[i].c;
		if(c[3].c3>MAX){c[3].c1%=NMAX;c[3].c2%=NMAX;c[3].c3%=NMAX;}
		c[0]=c[1];
		c[1]=c[2];
		c[2]=c[3];
		}
	aux=(c[3].c1%NMAX)*v[i].x+(c[3].c2%NMAX)*v[i].y+(c[3].c3%NMAX)*v[i].z;
	printf("%lu\n",aux%NMAX);
	c[0]=c0;c[1]=c1;c[2]=c2;
	}
return 0;
}