#include <fstream>
using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
int a,cn,n;
unsigned long long int expo(int a,int b){
    if(!b)return 1;
    if(b%2){
        return (a*expo(a,b-1))%n;
    }
    unsigned long long int p=expo(a,b/2);
    return (p*p)%n;
}
int main(){
    cin>>a>>cn;
    n=cn;
    int d=2,p,phi=1,prod;
    while(n>=2){
        p=0;
        prod=1;
        while(!(n%d))n/=d,p++,prod*=d;
        if(p)phi=phi*(d-1)*(prod/d);
        d++;
        if(d*d>n&&n>=2)d=n;
    }
    n=cn;
    phi--;
    cout<<expo(a,phi);
    return 0;
}