#include<stdio.h>
#define NMAX	666013
#define MM  1000000000UL
int main()
{
struct test{unsigned long x,y,z,a,b,c,n;};
test v[101];
unsigned long t,i,j,aux;
freopen("iepuri.in","r",stdin);
freopen("iepuri.out","w",stdout);
scanf("%lu",&t);
for(i=1;i<=t;i++)
	scanf("%lu%lu%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);
for(i=1;i<=t;i++)
	{
	for(j=3;j<=v[i].n;j++)
		{
		aux=v[i].z*v[i].a+v[i].y*v[i].b+v[i].x*v[i].c;
		v[i].x=v[i].y;v[i].y=v[i].z;
		if(aux<MM) v[i].z=aux;
		else v[i].z=aux%NMAX;
		}
	printf("%lu\n",aux%NMAX);
	}
return 0;
}