typedef long unsigned int size_t;


















 




 



 


 













 
















 
























typedef struct
{
  long int alloc;		 

  long int size;		 



  unsigned long int *d;		 
} __MP_INT;





typedef unsigned long int	mp_limb;
typedef long int		mp_limb_signed;
typedef mp_limb *		mp_ptr;

typedef const mp_limb *		mp_srcptr;



typedef long int		mp_size;

 


typedef struct
{
  __MP_INT  num;
  __MP_INT  den;

} MP_RAT;


void mp_set_memory_functions (void *(*) (size_t),
			      void *(*) (void *, size_t, size_t),
			      void (*) (void *, size_t));

 

void mpz_init (__MP_INT  *);
void mpz_set (__MP_INT  *, const __MP_INT  *);
void mpz_set_ui (__MP_INT  *, unsigned long int);
void mpz_set_si (__MP_INT  *, signed long int);
int mpz_set_str (__MP_INT  *, const char *, int);
void mpz_init_set (__MP_INT  *, const __MP_INT  *);
void mpz_init_set_ui (__MP_INT  *, unsigned long int);
void mpz_init_set_si (__MP_INT  *, signed long int);
int mpz_init_set_str (__MP_INT  *, const char *, int);
unsigned long int mpz_get_ui (const __MP_INT  *);
signed long int mpz_get_si (const __MP_INT  *);
char * mpz_get_str (char *, int, const __MP_INT  *);
void mpz_clear (__MP_INT  *);
void * _mpz_realloc (__MP_INT  *, mp_size);
void mpz_add (__MP_INT  *, const __MP_INT  *, const __MP_INT  *);
void mpz_add_ui (__MP_INT  *, const __MP_INT  *, unsigned long int);
void mpz_sub (__MP_INT  *, const __MP_INT  *, const __MP_INT  *);
void mpz_sub_ui (__MP_INT  *, const __MP_INT  *, unsigned long int);
void mpz_mul (__MP_INT  *, const __MP_INT  *, const __MP_INT  *);
void mpz_mul_ui (__MP_INT  *, const __MP_INT  *, unsigned long int);
void mpz_div (__MP_INT  *, const __MP_INT  *, const __MP_INT  *);
void mpz_div_ui (__MP_INT  *, const __MP_INT  *, unsigned long int);
void mpz_mod (__MP_INT  *, const __MP_INT  *, const __MP_INT  *);
void mpz_mod_ui (__MP_INT  *, const __MP_INT  *, unsigned long int);
void mpz_divmod (__MP_INT  *, __MP_INT  *, const __MP_INT  *, const __MP_INT  *);
void mpz_divmod_ui (__MP_INT  *, __MP_INT  *, const __MP_INT  *, unsigned long int);
void mpz_mdiv (__MP_INT  *, const __MP_INT  *, const __MP_INT  *);
void mpz_mdiv_ui (__MP_INT  *, const __MP_INT  *, unsigned long int);
void mpz_mmod (__MP_INT  *, const __MP_INT  *, const __MP_INT  *);
unsigned long int mpz_mmod_ui (__MP_INT  *, const __MP_INT  *, unsigned long int);
void mpz_mdivmod (__MP_INT  *, __MP_INT  *, const __MP_INT  *, const __MP_INT  *);
unsigned long int mpz_mdivmod_ui (__MP_INT  *, __MP_INT  *, const __MP_INT  *,
				  unsigned long int);
void mpz_sqrt (__MP_INT  *, const __MP_INT  *);
void mpz_sqrtrem (__MP_INT  *, __MP_INT  *, const __MP_INT  *);
int mpz_perfect_square_p (const __MP_INT  *);
int mpz_probab_prime_p (const __MP_INT  *, int);
void mpz_powm (__MP_INT  *, const __MP_INT  *, const __MP_INT  *, const __MP_INT  *);
void mpz_powm_ui (__MP_INT  *, const __MP_INT  *, unsigned long int, const __MP_INT  *);
void mpz_pow_ui (__MP_INT  *, const __MP_INT  *, unsigned long int);
void mpz_fac_ui (__MP_INT  *, unsigned long int);
void mpz_gcd (__MP_INT  *, const __MP_INT  *, const __MP_INT  *);
void mpz_gcdext (__MP_INT  *, __MP_INT  *, __MP_INT  *, const __MP_INT  *, const __MP_INT  *);
void mpz_neg (__MP_INT  *, const __MP_INT  *);
void mpz_com (__MP_INT  *, const __MP_INT  *);
void mpz_abs (__MP_INT  *, const __MP_INT  *);
int mpz_cmp (const __MP_INT  *, const __MP_INT  *);
int mpz_cmp_ui (const __MP_INT  *, unsigned long int);
int mpz_cmp_si (const __MP_INT  *, signed long int);
void mpz_mul_2exp (__MP_INT  *, const __MP_INT  *, unsigned long int);
void mpz_div_2exp (__MP_INT  *, const __MP_INT  *, unsigned long int);
void mpz_mod_2exp (__MP_INT  *, const __MP_INT  *, unsigned long int);
void mpz_and (__MP_INT  *, const __MP_INT  *, const __MP_INT  *);
void mpz_ior (__MP_INT  *, const __MP_INT  *, const __MP_INT  *);
void mpz_xor (__MP_INT  *, const __MP_INT  *, const __MP_INT  *);








void mpz_array_init (__MP_INT  [], size_t, mp_size);
void mpz_random (__MP_INT  *, mp_size);
void mpz_random2 (__MP_INT  *, mp_size);
size_t mpz_size (const __MP_INT  *);
size_t mpz_sizeinbase (const __MP_INT  *, int);

 

void mpq_init (MP_RAT *);
void mpq_clear (MP_RAT *);
void mpq_set (MP_RAT *, const MP_RAT *);
void mpq_set_ui (MP_RAT *, unsigned long int, unsigned long int);
void mpq_set_si (MP_RAT *, signed long int, unsigned long int);
void mpq_add (MP_RAT *, const MP_RAT *, const MP_RAT *);
void mpq_sub (MP_RAT *, const MP_RAT *, const MP_RAT *);
void mpq_mul (MP_RAT *, const MP_RAT *, const MP_RAT *);
void mpq_div (MP_RAT *, const MP_RAT *, const MP_RAT *);
void mpq_neg (MP_RAT *, const MP_RAT *);
int mpq_cmp (const MP_RAT *, const MP_RAT *);
void mpq_inv (MP_RAT *, const MP_RAT *);
void mpq_set_num (MP_RAT *, const __MP_INT  *);
void mpq_set_den (MP_RAT *, const __MP_INT  *);
void mpq_get_num (__MP_INT  *, const MP_RAT *);
void mpq_get_den (__MP_INT  *, const MP_RAT *);

 

mp_limb mpn_add (mp_ptr, mp_srcptr, mp_size, mp_srcptr, mp_size);
mp_size mpn_sub (mp_ptr, mp_srcptr, mp_size, mp_srcptr, mp_size);
mp_size mpn_mul (mp_ptr, mp_srcptr, mp_size, mp_srcptr, mp_size);
mp_size mpn_div (mp_ptr, mp_ptr, mp_size, mp_srcptr, mp_size);
mp_limb mpn_divmod_1 (mp_ptr, mp_srcptr, mp_size, mp_limb);
mp_limb mpn_mod_1 (mp_srcptr, mp_size, mp_limb);
mp_limb mpn_lshift (mp_ptr, mp_srcptr, mp_size, unsigned int);
mp_size mpn_rshift (mp_ptr, mp_srcptr, mp_size, unsigned int);
mp_size mpn_rshiftci (mp_ptr, mp_srcptr, mp_size, unsigned int, mp_limb);
mp_size mpn_sqrt (mp_ptr, mp_ptr, mp_srcptr, mp_size);
int mpn_cmp (mp_srcptr, mp_srcptr, mp_size);





 




























volatile void abort (void);







 































void *malloc (size_t);
void *realloc (void *, size_t);
void free (void *);

extern void *	(*_mp_allocate_func) (size_t);
extern void *	(*_mp_reallocate_func) (void *, size_t, size_t);
extern void	(*_mp_free_func) (void *, size_t);

void *_mp_default_allocate (size_t);
void *_mp_default_reallocate (void *, size_t, size_t);
void _mp_default_free (void *, size_t);

char *_mpz_get_str (char *, int, const __MP_INT  *);
int _mpz_set_str (__MP_INT  *, const char *, int);
void _mpz_impl_sqrt (__MP_INT  *, __MP_INT  *, const __MP_INT  *);


 






 







 








 

struct bases
{
   


  int chars_per_limb;

   



  mp_limb big_base;

   



  mp_limb big_base_inverted;

   
  float chars_per_bit_exactly;
};

extern const struct bases __mp_bases[37];

 





























 











































 






 































 








































 







 


 






extern

const

unsigned char __clz_tab[];









void

pow (const __MP_INT  *base, const __MP_INT  *exp, const __MP_INT  *mod, __MP_INT  *res)








{
  mp_ptr rp, ep, mp, bp;
  mp_size esize, msize, bsize, rsize;
  mp_size size;
  int mod_shift_cnt;
  int negative_result;
  mp_limb *free_me = 0L ;
  size_t free_me_size;

  esize = ( exp->size  >= 0 ?  exp->size  : - exp->size ) ;
  msize = ( mod->size  >= 0 ?  mod->size  : - mod->size ) ;
  size = 2 * msize;

  rp = res->d;
  ep = exp->d;

   




  mp = (mp_ptr) __builtin_alloca  (msize * 4 );
  do {	unsigned long int __xr = (  mod->d[msize - 1] );	unsigned int __a;	if (32   <= 32)	{	__a = __xr < (1<<2* (32   / 4) )	? (__xr < (1<< (32   / 4) ) ? 0 : (32   / 4) )	: (__xr < (1<<3* (32   / 4) ) ?  2* (32   / 4)  : 3* (32   / 4) );	}	else	{	for (__a = 32   - 8; __a > 0; __a -= 8)	if (((__xr >> __a) & 0xff) != 0)	break;	}	( mod_shift_cnt ) = 32   - (__clz_tab[__xr >> __a] + __a);	} while (0) ;
  if (mod_shift_cnt != 0)
    (void) mpn_lshift (mp, mod->d, msize, mod_shift_cnt);
  else
    do {	mp_size i;	for (i = 0; i < (  msize ); i++)	( mp )[i] = (  mod->d )[i];	} while (0) ;

  bsize = ( base->size  >= 0 ?  base->size  : - base->size ) ;
  if (bsize > msize)
    {
       

       

      bp = (mp_ptr) __builtin_alloca  ((bsize + 1) * 4 );
      do {	mp_size i;	for (i = 0; i < (  bsize ); i++)	( bp )[i] = (  base->d )[i];	} while (0) ;
       

      mpn_div (bp + msize, bp, bsize, mp, msize);
      bsize = msize;
      while (bsize > 0 && bp[bsize - 1] == 0)
	bsize--;
    }
  else
    {
      bp = base->d;
      bsize = ( base->size  >= 0 ?  base->size  : - base->size ) ;
    }

  if (res->alloc < size)
    {
       



      if (rp == ep || rp == mp || rp == bp)
	{
	  free_me = rp;
	  free_me_size = res->alloc;
	}
      else
	(*_mp_free_func) (rp, res->alloc * 4 );

      rp = (mp_ptr) (*_mp_allocate_func) (size * 4 );
      res->alloc = size;
      res->d = rp;
    }
  else
    {
       
      if (rp == bp)
	{
	   
	  bp = (mp_ptr) __builtin_alloca  (bsize * 4 );
	  do {	mp_size i;	for (i = 0; i < (  bsize ); i++)	( bp )[i] = (  rp )[i];	} while (0) ;
	}
      if (rp == ep)
	{
	   
	  ep = (mp_ptr) __builtin_alloca  (esize * 4 );
	  do {	mp_size i;	for (i = 0; i < (  esize ); i++)	( ep )[i] = (  rp )[i];	} while (0) ;
	}
      if (rp == mp)
	{
	   
	  mp = (mp_ptr) __builtin_alloca  (msize * 4 );
	  do {	mp_size i;	for (i = 0; i < (  msize ); i++)	( mp )[i] = (  rp )[i];	} while (0) ;
	}
    }

  if (esize == 0)
    {
      rp[0] = 1;
      res->size = 1;
      return;
    }

  do {	mp_size i;	for (i = 0; i < (  bsize ); i++)	( rp )[i] = (  bp )[i];	} while (0) ;
  rsize = bsize;

  {
    mp_size i;
    mp_size xsize;
    mp_ptr dummyp = (mp_ptr) __builtin_alloca  ((msize + 1) * 4 );
    mp_ptr xp = (mp_ptr) __builtin_alloca  (2 * (msize + 1) * 4 );
    int c;
    mp_limb e;
    mp_limb carry_limb;

    negative_result = (ep[0] & 1) && base->size < 0;

    i = esize - 1;
    e = ep[i];
    do {	unsigned long int __xr = (  e );	unsigned int __a;	if (32   <= 32)	{	__a = __xr < (1<<2* (32   / 4) )	? (__xr < (1<< (32   / 4) ) ? 0 : (32   / 4) )	: (__xr < (1<<3* (32   / 4) ) ?  2* (32   / 4)  : 3* (32   / 4) );	}	else	{	for (__a = 32   - 8; __a > 0; __a -= 8)	if (((__xr >> __a) & 0xff) != 0)	break;	}	( c ) = 32   - (__clz_tab[__xr >> __a] + __a);	} while (0) ;
    e <<= (c + 1);		 
    c = 32  - 1 - c;

     








    for (;;)
      {
	while (c != 0)
	  {
	    mp_ptr tp;
	    mp_size tsize;

	    xsize = mpn_mul (xp, rp, rsize, rp, rsize);
	    mpn_div (dummyp, xp, xsize, mp, msize);

	     
	    if (xsize > msize)
	      xsize = msize;
	    while (xsize > 0 && xp[xsize - 1] == 0)
	      xsize--;

	    tp = rp; rp = xp; xp = tp;
	    tsize = rsize; rsize = xsize; xsize = tsize;

	    if ((mp_limb_signed) e < 0)
	      {
		if (rsize > bsize)
		  xsize = mpn_mul (xp, rp, rsize, bp, bsize);
		else
		  xsize = mpn_mul (xp, bp, bsize, rp, rsize);
		mpn_div (dummyp, xp, xsize, mp, msize);

		 
		if (xsize > msize)
		  xsize = msize;
		while (xsize > 0 && xp[xsize - 1] == 0)
		  xsize--;

		tp = rp; rp = xp; xp = tp;
		tsize = rsize; rsize = xsize; xsize = tsize;
	      }
	    e <<= 1;
	    c--;
	  }

	i--;
	if (i < 0)
	  break;
	e = ep[i];
	c = 32 ;
      }

     





    carry_limb = mpn_lshift (res->d, rp, rsize, mod_shift_cnt);
    rp = res->d;
    if (carry_limb != 0)
      {
	rp[rsize] = carry_limb;
	rsize++;
      }
    mpn_div (dummyp, rp, rsize, mp, msize);
     
    if (rsize > msize)
      rsize = msize;
    while (rsize > 0 && rp[rsize - 1] == 0)
      rsize--;
    rsize = mpn_rshift (rp, rp, rsize, mod_shift_cnt);
  }

  res->size = negative_result >= 0 ?  rsize : -rsize;

  if (free_me != 0L )
    (*_mp_free_func) (free_me, free_me_size * 4 );

  __builtin_alloca  (0);
}