#include <cstdio>

#define MOD 666013

using namespace std;

int mi[4][4];
int m1[4][4];

inline int inmultire_matrici( int a[4][4], int b[4][4], int p )
{
  int mat[4][4];

  for( int i=1;i<=3;i++ )
    for( int j=1;j<=3;j++ )
    {
      mat[i][j]=0;

      for( int l=1;l<=3;l++ )
        mat[i][j]=(mat[i][j]+1LL*a[i][l]*b[l][j]%MOD)%MOD;
    }

  if( p )
  {
    for( int i=1;i<=3;i++ )
      for( int j=1;j<=3;j++ )
        mi[i][j]=mat[i][j];
  }
  else
  {
    for( int i=1;i<=3;i++ )
      for( int j=1;j<=3;j++ )
        m1[i][j]=mat[i][j];
  }
}

int rpl( int pow )
{
  while( pow )
    if( pow%2==1 )
    {
      inmultire_matrici(m1,mi,1);
      pow--;
    }
    else
    {
      inmultire_matrici(m1,m1,0);
      pow/=2;
    }
}

int main()
{
  freopen( "iepuri.in", "r", stdin );
  freopen( "iepuri.out", "w", stdout );

  int t, x, y, z, a, b, c, n;

  scanf( "%d", &t );

  while( t )
  {
    scanf( "%d%d%d%d%d%d%d", &x, &y, &z, &a, &b, &c, &n );

    m1[1][3]=c;
    m1[2][3]=b;
    m1[3][3]=a;
    m1[2][1]=m1[3][2]=1;
    m1[1][1]=m1[1][2]=m1[2][2]=m1[3][1]=0;

    mi[1][1]=mi[2][2]=mi[3][3]=1;
    mi[1][2]=mi[1][3]=mi[2][1]=mi[2][3]=mi[3][2]=mi[3][3]=0;

    rpl(n);

    m1[1][1]=x;
    m1[1][2]=y;
    m1[1][3]=z;
    m1[2][2]=m1[3][1]=m1[2][1]=m1[2][3]=m1[3][2]=m1[3][3]=0;

    inmultire_matrici(m1,mi,1);

    printf( "%d\n", mi[1][1] );

    t--;
  }

  return 0;
}