#include <stdio.h>
#include <stdlib.h>

#define FILE_IN "inversmodular.in"
#define FILE_OUT "inversmodular.out"

// problema cu invers modular de pe infoarena

// teste de baza:

// 5 7 rez = 3

// 4 9 rez = 7, mie imi da 4

unsigned int phi ( unsigned int x )
{
  unsigned int rez = x;
  
  for ( unsigned int i = 2; i * i < x; i++ )
    {
      if ( x % i == 0 )
	{
	  while ( x % i == 0 )
	    x /= i;
	  rez -= ( rez / i );
	}
    }

  if ( x > 1 )
    rez -= rez / x;

  return rez;
}

unsigned int tl_mod(unsigned int base, unsigned int exp, unsigned int mod)
{
    unsigned long long rez = 1;
    unsigned long long base_mod = base;

    while (exp > 0)
    {
        if (exp & 1)
	  {
	    rez = (rez * base_mod) % mod;
	  }
        base_mod = (base_mod * base_mod) % mod;
        exp >>= 1;
    }

    return (unsigned int) rez;
}

int main ( void )
{
  FILE *fin, *fout;
  fin = fopen ( FILE_IN, "r" );
  fout = fopen ( FILE_OUT, "w" );
  if ( fin == NULL || fout == NULL )
    {
      perror ( "Eroare la deschidere fisiere\n" );
      exit ( -1 );
    }

  unsigned int a, n;
  fscanf ( fin, "%u %u", &a, &n );
  
  unsigned int rez = tl_mod ( a, phi ( n ) - 1, n );
  fprintf ( fout, "%u\n", rez );
  
  if ( ( fclose ( fin ) ) != 0 || ( fclose ( fout ) ) != 0 )
    {
      perror ( "Eroare la inchidere fisiere\n" );
      exit ( -2 );
    }
  return 0;
}