#include<stdio.h>
#define infile "iepuri.in"
#define outfile "iepuri.out"
#define modulo 666013
long long z[1][3]; //nr-ul de iepuri din ultimele 3 zile
long long x[3][3]; //matricea cu care inmultim

void inmultire(long long a[3][3], long long b[3][3], long long c[3][3], int x, int y)
	{
	long long d[3][3];
	int i,j,k;
	for(i=0;i<x;i++) //linia
		for(j=0;j<y;j++) //coloana
			{
			d[i][j]=0;
			for(k=0;k<y;k++)
				d[i][j]=(d[i][j]+a[i][k]*b[k][j])%modulo;
			}
	for(i=0;i<x;i++)
		for(j=0;j<y;j++)
			c[i][j]=d[i][j]; //punem in c
	}

int ridica_putere(int p)
	{
	while(p) //trebuie sa ridicam la puterea p
		{
		if(p%2) inmultire(z,x,z,1,3); //z=z*x
		inmultire(x,x,x,3,3); //x=x^2
		p/=2;
		}
	return z[0][2];
	}

int main()
{
int t,n;
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);


scanf("%d\n",&t); //numarul de teste
while(t--) //testam
	{
	x[1][0]=x[2][1]=1; //cele doua pozitii cu 1 din matricea principala
	x[0][0]=x[0][1]=x[1][1]=x[2][0]=0; //pozitiile cu 0
	scanf("%d %d %d",&z[0][0],&z[0][1],&z[0][2]);
	scanf("%d %d %d",&x[2][2],&x[1][2],&x[0][2]); //cele 3 valori de multiplicare
	scanf("%d",&n); //ziua la care trebuie sa aflam numarul de iepuri
	printf("%d\n",ridica_putere(n-2));
	}


fclose(stdin);
fclose(stdout);
return 0;
}