#include <fstream>
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
int m;
int putere(int x, int n)
{
    int p=1;
    while(n>0)
    {
        if(n%2==1)
        {
            p=p*x;
            p%=m;
            n--;
        }
        x*=x;
        x%=m;
        n/=2;

    }
    return p;
}

int phi(int n)
{
    int ans = n;
    for(int i = 2; i * i <= n; i++)
        if(n % i == 0)
        {
            while(n % i == 0)
                n /= i;
            ans = ans / i * (i - 1);
        }
    if(n != 1)
        ans = ans / n * (n - 1);
    return ans;
}
int main()
{
    int a,n,put;
    in>>a>>n;
    m=n;
    put=phi(n);
    //cout<<a<<" "<<put-1<<endl;
    out<<putere(a,put-1)%m;
    return 0;
}