#include <fstream>
#define mod 666013
using namespace std;
ifstream f("iepuri.in");
ofstream g("iepuri.out");

long long m[4][4],zi[4],c[4][4];
long long t,n,nr;

void initializare()
{
  for (int i=1; i<=3; i++)
	for (int j=1; j<=3; j++)
	  m[i][j]=0;
  m[2][1]=1; m[3][2]=1;
}

void cut (long long src[][4], long long dest[][4])
{
  for (int i=1; i<=3; i++)
	for (int j=1; j<=3; j++)
	{
	  dest[i][j]=src[i][j];
	  src[i][j]=0;
	}
}

void inmulteste (long long a[][4],long long b[][4])
{
  for (int i=1; i<=3; i++)
	for (int j=1; j<=3; j++)
	  for (int k=1; k<=3; k++)
		c[i][j]=(c[i][j]+(a[i][k]*b[k][j])%mod)%mod;
  cut (c,a);
}


void power (long long m[][4],long long p)
{
  long long sol[4][4]={{0,0,0},{0,1,0,0},{0,0,1,0},{0,0,0,1}}; //sol-matricea identica de ordinul 3
  for (long long aux=1; aux<=p; aux*=2)   //nu putem folosi varianta (1<<i) pentru ca se pare ca pentru i>31 nu merge !!!
  { 
	if ((aux&p)>0)          
	  inmulteste (sol,m);       
	inmulteste (m,m);
  }
  cut (sol,m);
}

int main ()
{
  f>>t;
  for (int i=1; i<=t; i++)
  {
	nr=0;
	initializare ();
	f>>zi[3]>>zi[2]>>zi[1]>>m[1][1]>>m[1][2]>>m[1][3]>>n;
	power (m,n-2);
	for (int j=1; j<=3; j++)
	  nr=(nr+(m[1][j]*zi[j])%mod)%mod;
	g<<nr<<'\n';
  }
  f.close (); g.close (); return 0;
}

/*recursiv
void pow(a[][4],int n) {
  if(n==0) {
    a[0][0]=a[1][1]=a[2][2]=1;
    a[0][1]=a[0][2]=a[1][0]=a[1][2]=a[2][0]=a[2][1]=0;
  }
  else
   if(n%2) {
     pow(a,n-1);
     inmulteste(m,a);
   }
   else {
     pow(a,n/2);
     inmulteste(a,a);
   }
}
*/