#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

#define ll long long

ll A,N;

ll putere (ll baza, ll exponent)
{
    ll p,sol=1;
    for (p=1;p<=exponent;p*=2)
    {
        if (p&exponent)
        {
            sol=(sol*baza)%N;
        }
        baza=(baza*baza)%N;
    }
    return sol;
}

int main()
{
    fin >> A >> N;
    ll phi=N,nr=N;
    ll i;
    for (i=2;i*i<=nr;++i)
    {
        if (nr%i==0)
        {
            while (nr%i==0)
            {
                nr/=i;
            }
            phi=(phi/i)*(i-1);
        }
    }
    if (phi!=1)
    {
        phi=phi/nr*(nr-1);
    }
    --phi;
    fout << 1LL*putere(A,phi);
    fin.close();
    fout.close();
    return 0;
}