#include <fstream>

using namespace std;

ifstream cin ("inversmodular.in");
ofstream cout ("inversmodular.out");
int c;
long long exponentiere(long long a, int n){

if(n==0)
    return 1;
long long aux = exponentiere(a,n/2);
aux = (aux * aux)%c;
if(n%2==1)
    aux = (aux * a)%c;
return aux;

}

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

int main()  {
    int a,n;
    cin>>a>>n;
    c=n;
    cout << exponentiere(a, phi(n) - 1);
    return 0;
}