#include<cstdio>
#define ll long long
#define m 666013
using namespace std;
ll h[3][3],sol[3][3],h3[3][1],C[3][3];
int pas,x,y,z,a,b,c,n,p;
inline void im()
{for(register int i=0;i<3;++i) 
	for(register int j=0;j<3;++j)
		{C[i][j]=0;
		 for(register int k=0;k<3;++k)
			 C[i][j]=(C[i][j]+(sol[i][k]*h[k][j])%m)%m;  
		} 
 for(register int i=0;i<3;++i) 
	for(register int j=0;j<3;++j)
		sol[i][j]=C[i][j];
}
inline void in()
{for(register int i=0;i<3;++i) 
	for(register int j=0;j<3;++j)
		{C[i][j]=0;
		 for(register int k=0;k<3;++k)
			 C[i][j]=(C[i][j]+(h[i][k]*h[k][j])%m)%m;  
		} 
 for(register int i=0;i<3;++i) 
	for(register int j=0;j<3;++j)
		h[i][j]=C[i][j];
}
int main()
{freopen("iepuri.in","rt",stdin);
 freopen("iepuri.out","wt",stdout);
 scanf("%d",&pas);
 for(;pas--;)
	 {scanf("%d%d%d%d%d%d%d",&x,&y,&z,&a,&b,&c,&n); p=n-3;
	  h[0][0]=a; h[0][1]=b; h[0][2]=c; h[1][0]=h[2][1]=1;
	  h[1][1]=h[1][2]=h[2][0]=h[2][2]=0;
	  for(register int i=0;i<3;++i) 
		for(register int j=0;j<3;++j)
			sol[i][j]=(i==j)*1;
	  h3[0][0]=a*z+b*y+c*x;
	  h3[1][0]=z; h3[2][0]=y;
	  for (;p;p>>=1)  
		{if ( p&1 ) im();                 
		 in();
		}
	  printf("%lld\n", sol[0][0]*h3[0][0] + sol[0][1] * h3[1][0] + sol[0][2] * h3[2][0]);
	 }
 return 0;
}