#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];
int 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],int 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 (int i=0; (1<<i)<=p; i++)   
  { 
	if (((1<<i)&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;
}