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

int indEuler( int n ) {
  int euler, d;

  euler = n;
  d = 2;

  while ( d * d <= n ) {
    if ( n % d == 0 ) {
      euler = euler / d * ( d - 1 );
      while ( n % d == 0 )
        n = n / d;
    }
    d++;
  }

  if ( n > 1 )
    euler = euler / n * ( n - 1 );

  return euler;
}

int main()
{
    FILE *fin, *fout;
    long long num_a, rez;
    int num_n, put;

    fin = fopen( "inversmodular.in", "r" );
    fscanf( fin, "%lld%d", &num_a, &num_n );
    fclose( fin );

    put = indEuler( num_n ) - 1;
    rez = 1;
    while ( put > 0 ) {
      if ( put % 2 == 1 )
        rez = rez * num_a % num_n;
      num_a = num_a * num_a % num_n;
      put = put / 2;
    }

    fout = fopen( "inversmodular.out", "w" );
    fprintf( fout, "%lld\n", rez );
    fclose( fout );
    return 0;
}