#include <fstream>

using namespace std;

ifstream cin ("inversmodular.in");
ofstream cout ("inversmodular.out");

long long n;

long long lgput(long long baza,int exp){
    if(exp==0)
        return 1;
    long long aux=lgput(baza,exp/2);
    if(exp%2==1)
        aux=(aux*aux%n*baza)%n;
    else
        aux=(aux*aux)%n;
    return aux;
}

long long phi(long long x)  {
    long long ans = 1;
    for (long long i = 2; i * i <= x; ++i)    {
        if (x % i == 0) {
            int nr = 0;
            while (x % i == 0)  {
                x /= i;
                ++nr;
            }
            ans *= ((i - 1) * lgput(i, nr - 1)) % n;
            ans %= n;
        }
    }
    if (x > 1)  {
        ans *= (x - 1);
        ans %= n;
    }
    return ans;
}

int main()  {
    int a;
    cin>>a>>n;
    cout<<lgput(a,phi(n) - 1);

    return 0;
}