#include <bits/stdc++.h>

using namespace std;

int euler(int n)
{
        int res=1;
        for(int p=2;p*p<=n;p++)
        {
                int cur=1;
                while(n%p==0)
                {
                        cur*=p;
                        n/=p;
                }
                res*=(cur-cur/p);
        }
        if(n>1)
        {
                res*=(n-1);
        }
        return res;
}

int a,mod;

int add(int a,int b)
{
        a+=b;
        if(a>=mod)
        {
                a-=mod;
        }
        if(a<0)
        {
                a+=mod;
        }
        return a;
}

int mul(int a,int b)
{
        return a*(long long)b%mod;
}

int expow(int a,int b)
{
        int res=1;
        while(b)
        {
                if(b&1)
                {
                        res=mul(res,a);
                }
                a=mul(a,a);
                b>>=1;
        }
        return res;
}

int main()
{
        freopen("inversmodular.in","r",stdin);
        freopen("inversmodular.out","w",stdout);
        cin>>a>>mod;
        a%=mod;
        int inv=expow(a,euler(mod)-1);
        cout<<inv<<"\n";
        return 0;
}