#include<cstdio>
using namespace std;
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    long long n,a,ans=1;
    scanf( "%lld%lld" , &a,&n );
    for ( int bit = 0 ; (1ll<<bit) <= n-2 ; ++bit ){
        if ( n-2 & (1ll<<bit) )
            ans = ans * a % n;
        a = a * a % n;
    }
    printf ("%lld",ans);
    return 0;
}