#include <cstdio>
using namespace std;

int phi( int n ){
    int nr=n, i;
    for( i=2; i*i<=n; ++i)
        if ( n%i==0 ){
            while( n%i==0 )n/=i;
            nr=(nr/i)*(i-1);
        }
    if( n!=1 )nr=nr/n*(n-1);
    return nr;
}

int put(long long a, long long b, int c){
    int p=1;
    while(b!=0){
        if(b%2==1){
            p=(p*a)%c;
            --b;
        }
        a=(a*a)%c;
        b/=2;
    }
    return p;
}

int main(){
    freopen( "inversmodular.in", "r", stdin );
    freopen( "inversmodular.out", "w", stdout );
    int n, a;
    scanf( "%d%d", &n, &a );
    printf( "%d", put( n, phi(a) - 1, a ) );
    return 0;
}