#include <fstream>

using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
int a, p;
long long exp_log(int x)
{
    if(x==0)
        return 1;
    if(x%2==0)
        return (exp_log(x/2)%p)*(exp_log(x/2)%p)%p;
    else
        return (exp_log(x-1)%p)*a%p;
}
int main()
{
    cin>>a>>p;
    int copie=p, fi=p, div=2;
    while(copie>1)
    {
        if(copie%div==0)
        {
            fi=fi/div*(div-1);
            while(copie%div==0)
                copie/=div;
        }
        div++;
        if(div*div>copie)
            div=copie;
    }
    cout<<exp_log(fi-1);
    return 0;
}