#include <fstream>
#include <algorithm>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
long long a,n,fi,nc,d,sol;
int main()
{
    fin>>a>>n;
    fi=1;nc=n;
    if(n%2==0)
    {
        n/=2;
        while(n%2==0)
        {
            fi*=2;
            n/=2;
        }
    }
    for(d=3;d*d<=n;d+=2)
        if(n%d==0)
        {
            fi*=d-1;
            n/=d;
            while(n%d==0)
            {
                fi*=d;
                n/=d;
            }
        }
    if(n>1)fi*=n-1;
    fi--;
    sol=1;
    n=nc;
    for(;fi;fi/=2)
    {
        if(fi%2)sol=(sol*a)%n;
        a=(a*a)%n;
    }
    fout<<sol;


    return 0;
}