#include <stdio.h>
#define modul 666013

typedef long long int lli;

int t;
lli n, x, y, z, a, b, c, sol, cf[4][4], cfn[4][4], cfx[4][4];

void
patr ()
{
  int i, j, k;
  for (i = 1; i <= 3; i++)
    for (j = 1; j <= 3; j++)
      cfx[i][j] = 0;
  for (k = 1; k <= 3; k++)
    for (i = 1; i <= 3; i++)
      for (j = 1; j <= 3; j++)
	cfx[i][j] += cfn[i][k] * cfn[k][j];
  for (i = 1; i <= 3; i++)
    for (j = 1; j <= 3; j++)
      cfn[i][j] = cfx[i][j] % modul;
}

void
inm ()
{
  int i, j, k;
  for (i = 1; i <= 3; i++)
    for (j = 1; j <= 3; j++)
      cfx[i][j] = 0;
  for (k = 1; k <= 3; k++)
    for (i = 1; i <= 3; i++)
      for (j = 1; j <= 3; j++)
	cfx[i][j] += cf[i][k] * cfn[k][j];
  for (i = 1; i <= 3; i++)
    for (j = 1; j <= 3; j++)
      cfn[i][j] = cfx[i][j] % modul;
}

void
putere (lli x)
{
  if (x)
    {
      if (x % 2)
	{
	  putere (x - 1);
	  inm ();
	}
      else
	{
	  putere (x /2);
	  patr ();
	}
    }
}

int
main ()
{
  FILE *fi = fopen ("iepuri.in", "r"), *fo = fopen ("iepuri.out", "w");
  lli i, j, x1, y1, z1;
  for (fscanf (fi, "%d", &t); t; t--)
    {
      fscanf (fi, "%lld %lld %lld %lld %lld %lld %lld", &x, &y, &z, &a, &b,
	      &c, &n);
      cf[1][1] = 0;
      cf[1][2] = 1;
      cf[1][3] = 0;
      cf[2][1] = 0;
      cf[2][2] = 0;
      cf[2][3] = 1;
      cf[3][1] = c;
      cf[3][2] = b;
      cf[3][3] = a;
      for (i = 1; i <= 3; i++)
	for (j = 1; j <= 3; j++)
	  if (i == j)
	    cfn[i][j] = 1;
	  else
	    cfn[i][j] = 0;
      putere (n);
      fprintf (fo, "%lld\n",
	       (x * cfn[1][1] + y * cfn[1][2] + z * cfn[1][3]) % modul);
    }
  fclose (fi);
  fclose (fo);
  return (0);
}