#include<fstream.h>
#include<stdio.h>
#define ko 666013
long long vect[33][4][4],a,b,c,x,y,z,j,n,nr,v[4][4],v1[4][4];

long long form()
{long long k,i,j,j1;
 memset(vect,0,sizeof(vect));
 vect[0][1][1]=c;vect[0][2][1]=(a*c)%ko;  vect[0][3][1]=(b*c+a*a*c)%ko;
 vect[0][1][2]=b;vect[0][2][2]=(a*b+c)%ko;vect[0][3][2]=(b*b+a*c+a*a*b)%ko;
 vect[0][1][3]=a;vect[0][2][3]=(a*a+b)%ko;vect[0][3][3]=(c+b*a+a*b+a*a*a)%ko;
 for(k=1;k<=32;k++)
   for(i=1;i<=3;i++)
	for(j=1;j<=3;j++)
	  for(j1=1;j1<=3;j1++)
		vect[k][i][j]=(vect[k][i][j]+vect[k-1][i][j1]*vect[k-1][j1][j])%ko;
 return k-1;
 //vect[k][i][j]=incepe pe poz 3*2^(k-1) al i lea termen si al jlea

 }
void rezolva()
 {long long nr,i,j,k,j1;
 n-=2;
 nr=form();
 memset(v,0,sizeof(v));
 memset(v1,0,sizeof(v1));
 v[1][1]=1;v[2][2]=1;v[3][3]=1;
 while(n>=3)
  {for(k=nr;k>=0;k--)
	if((long long)3*1<<k<=n)
	  {memset(v1,0,sizeof(v1));
	   n-=(long long)3*1<<k;
	   for(i=1;i<=3;i++)
		 for(j=1;j<=3;j++)
		   for(j1=1;j1<=3;j1++)
			 v1[i][j]=(v1[i][j]+v[i][j1]*vect[k][j1][j])%ko;
	   memcpy(v,v1,sizeof(v1));
	   }
   }



 if(n==0)
  printf("%lld\n",(x*v[3][1]+y*v[3][2]+z*v[3][3])%ko);
 else
  {k=0;
   n-=3*1<<k;
   memset(v1,0,sizeof(v1));
	   for(i=1;i<=3;i++)
		 for(j=1;j<=3;j++)
		   for(j1=1;j1<=3;j1++)
			 v1[i][j]=(v1[i][j]+v[i][j1]*vect[k][j1][j])%ko;
	   memcpy(v,v1,sizeof(v1));
   }
  if(n==-1)
   printf("%lld\n",(x*v[2][1]+y*v[2][2]+z*v[2][3])%ko);
  if(n==-2)
   printf("%lld\n",(x*v[1][1]+y*v[1][2]+z*v[1][3])%ko);
 }
void rezolva1()
{long long i,aa[1000];
 aa[0]=x;aa[1]=y;aa[2]=z;
 for(i=3;i<=n;i++)
  aa[i]=(aa[i-1]*a+aa[i-2]*b+aa[i-3]*c)%ko;
 printf("%lld\n",aa[n]);
 }



int main()
{long long k,i,j,j1,t;
 freopen("iepuri.in","r",stdin);
 freopen("iepuri.out","w",stdout);
 scanf("%lld",&t);
 for(i=1;i<=t;i++)
  {
  scanf("%lld%lld%lld%lld%lld%lld%lld",&x,&y,&z,&a,&b,&c,&n);
  rezolva1();
  rezolva();
  }

 fclose(stdout);
 return 0;
 }