#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;
}

long long put( int n, int p , int a ){
    if( p==1 )return n%a;
    long long x=put( n, p/2 , a);
    if( p%2==0 )return 1LL * x*x%a;
    return n*put( n, p-1, a ) % a;
}

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;
}