#include <bits/stdc++.h>

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

long long unsigned LogPow(long long unsigned b, long long unsigned p,long long &Mod)
{
    if(b==0)
        return 0;
    if(b==1)
        return 1;
    if(p==0)
        return 1;
    if(p==1)
        return b;
    if(p%2==0)
    {
        return LogPow((b*b)%Mod,p/2,Mod);
    }
    else
    {
        return (LogPow(b,p-1,Mod)*b)%Mod;
    }
}

long long unsigned Phi(long long unsigned n)
{
    long long unsigned nr=n;
    for(long long unsigned 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;
}

int main()
{
    long long n, Mod;
    fin>>n>>Mod;
    fout<<LogPow(n,Phi(Mod)-1,Mod)<<'\n';
    return 0;
}