#include <bits/stdc++.h>
using namespace std ;
ifstream fin("inversmodular.in") ;
ofstream fout("inversmodular.out") ;
#define ll long long int
ll phi(ll n)
{
    ll r=n,d=2 ;
    while(n>1)
    {
        if(n%d==0)
        {
            r=r/d*(d-1) ;
            while(n%d==0) n/=d ;
        }
        d++ ;
        if(d*d>n) d=n ;
    }
    return r ;
}
int main()
{
    ll n,a,rasp=1 ;
    fin>>a>>n ;
    ll put=phi(n)-1 ;
    for(int i=1;i<=put;i<<=1){
        if(i&put) rasp=(rasp*a)%n ;
        a=(a*a)%n ;
    }
    fout<<rasp ;
    return 0 ;
}