#include <iostream>

using namespace std;

long long P(int a, int n)
{
    long long p=1;
    while(n)
    {
        if(n%2==1)
            p=p*a;
        a=a*a;
        n/=2;
    }
    return p;
}

int Phi(int n)
{
    int r=n, d=2;
    while(n>1)
    {
        if(n%d==0)
        {
            r=r/d*(d-1);
            while(n%d==0)
                n/=d;
        }
        d++;
        if(d*d>n)
            d=n;
    }
    return r;
}

int main()
{
    int a, n;
    cin >> a >> n;
    // Inversul moduelar a lui a
    long long x = P(a,Phi(n)-1);
    cout << x%n;
    return 0;
}