#include <iostream>
#include <fstream>
using namespace std;
int mod;
long long putere(long long n, long long p)
{
    if(p==0)
        return 1;
    long long y=putere(n,p/2);
    if(p%2==0)
        return y*y%mod;
    return y*y%mod*n%mod;
}
long long phi (int n)
{
    long long rez=n,i;
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            while(n%i==0)
                n/=i;
            rez=(rez/i)*(i-1);
        }
    }
    if(n!=1)
        rez=(rez/n)*(n-1);
    return rez;
}
int main()
{
    ifstream fin ("inversmodular.in");
    ofstream fout ("inversmodular.out");
    int a,n,exp;
    fin>>a>>n;
    mod=n;
    exp=phi(n)-1;
    fout<<putere(a,exp);
    return 0;
}