#include <cstdio>
#include <fstream>
#include <cstring>

using namespace std;

#define m 666013

void prd (int a[4][4],int b[4][4]){
	
	int c[4][4];
	memset(c,0,sizeof(c));
	for(int k=1;k<=3;++k)
	for(int i=1;i<=3;++i)
	for(int j=1;j<=3;++j)
	c[k][i]=(c[k][i]+1ll*a[k][j]*b[j][i])%m;
	memcpy(a,c,sizeof(c));
	
	}

int main ()
{
	
	int a[4][4],b[4][4],t,n,x,y,z,i,v[64];
	ifstream in ("iepuri.in");
	freopen ("iepuri.out","w",stdout);
	for(in>>t;t;--t){
		memset(a,0,sizeof(a));
		in>>x>>y>>z>>a[1][1]>>a[1][2]>>a[1][3]>>n;
		a[2][1]=a[3][2]=1,n-=2;
		memcpy(b,a,sizeof(a));
		for(i=0;n;n>>=1)
			v[++i]=n%2;
		for(--i;i;--i){
			prd(a,a);
			if(v[i])
				prd(a,b);	
			}
		printf("%lld\n",(1ll*z*a[1][1]%m+1ll*y*a[1][2]%m+1ll*x*a[1][3])%m);
	}
	
	return 0;}