#include <bits/stdc++.h>

using namespace std;

long long a,n,x,fi,s,p[1000005];

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

int main()
{
    ifstream in("inversmodular.in");
    ofstream out("inversmodular.out");
    in >> a >> 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--;
    out << power(a,fi-1);

}