#include<stdio.h>
#include<string.h>
#define M 666013
#define K 3
long long a[K][K];
long long b[K][K];
long long v[K];
long long A,B,C;
int n;
inline void inmultesc(long long a[K][K],long long b[K][K])
{
	long long c[K][K]={0};
	for(int i=0; i<K; ++i)
	{
		for(int j=0; j<K; ++j)
		{
			for(int k=0; k<K; ++k)
			{
				c[i][j]+=a[i][k]*b[k][j];
				c[i][j]%=M;
			}
		}
	}
	memcpy(a,c,sizeof(c));
}
inline void init()
{
	scanf("%lld%lld%lld%lld%lld%lld%d",&v[2],&v[1],&v[0],&A,&B,&C,&n);

	a[0][0]=A;
	a[0][1]=B;
	a[0][2]=C;
	a[1][0]=a[2][1]=1;
	a[1][1]=a[1][2]=a[2][0]=a[2][2]=0;

	b[0][0]=b[1][1]=b[2][2]=1;
	b[0][1]=b[0][2]=b[1][0]=b[1][2]=b[2][0]=b[2][1]=0;

	n-=2;
}
inline void rezolva()
{
	for(; n!=0; n>>=1)
	{
		if((n&1)==1)
			inmultesc(b,a);
		inmultesc(a,a);
	}

	long long rez=0;
	for(int i=0; i<K; ++i)
		rez+=(b[0][i]*v[i]);
	rez%=M;

	printf("%lld\n",rez);
}
int main()
{
	freopen("iepuri.in","r",stdin);
	freopen("iepuri.out","w",stdout);
	int T;
	scanf("%d",&T);
        for(; T; --T)
	{
		init();
		rezolva();
	}
	return 0;
}