#include <stdio.h>

int phi( int n ){
    int i, rez = n;
    for( i = 2; i * i <= n; i++ ){
        if ( n % i == 0 ){
            rez /= i;
            rez *= ( i - 1 );
        }
        while ( n % i == 0 )    n /= i;
    }
    if( n > 1 ){
        rez /= n;
        rez *= ( n - 1 );
    }
    return rez;
}
int lgexp( int a, int b, int mod ){
   int rez = 1;
   while ( b > 0 ){
        if ( b & 1 ){
            rez = ( (long long)a * (long long)rez ) % mod;
        }
        b /= 2;
        a = ( (long long)a * (long long)a ) % mod;;
    }
    return rez;
}

int main()
{
    FILE *in = fopen ( "inversmodular.in", "r" );
    int n, m;
    fscanf ( in, "%d%d", &n, &m );
    fclose ( in );
    FILE *out = fopen ( "inversmodular.out", "w" );
    fprintf ( out, "%d", lgexp( n, phi( m ) - 1, m ) );
    fclose ( out );
    return 0;
}