#include <fstream>
using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
int phi(int x)
{
    int euler=x,f,p;
    f=2;
    while(f*f<=x)
    {
        p=0;
        while(x%f==0)
        {
            p++; x/=f;
        } if(p>0) euler=euler/f*(f-1);
        f++;
    } if(x>1) euler=euler/x*(x-1);
    return euler;
}
long long fast_pow_mod(int a,int b,int n)
{
    long long aa=a,p;
    for(p=1;b;b=b>>1){
        if(b&1) p=(p*aa)%n;
    aa=(aa*aa)%n;}
    return p;
}
int invers_modular(int a,int n)
{
    return fast_pow_mod(a,phi(n)-1,n);
}
int main()
{
    int a,n;
    cin>>a>>n;
    cout<<invers_modular(a,n);
    return 0;
}