#include <bits/stdc++.h>

using namespace std;

long long a,n,x,fi,s,t;

long long power(long long a, long long p){
    if(p==1) return a%t;
    if(p%2==0) return power(a*a%t,p/2%t)%t;
    if(p%2==1) return a%n*power(a*a%t,(p-1)/2%t)%t;
}

int main()
{
    ifstream in("inversmodular.in");
    ofstream out("inversmodular.out");
    in >> a >> n;
    t=n;
    s=sqrt(n);
    fi=n;
    for(int i=2;i<=s;i++){
        if(n%i==0){
            while(n%i==0) n/=i;
            fi/=i;
            fi*=(i-1);
        }
    }
    if(n>1) fi/=n, fi*=(n-1);
    out << power(a,fi-1);

}