#include <bits/stdc++.h>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

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

int main(){
    long long a, n;
    f >> a >> n;
    long long MOD=n;
    long long put=phi(n)-1;
    long long p=1;
    while(put){
        if(put%2){
            p=(p*a)%MOD;
        }
        a=(a*a)%MOD;
        put/=2;
    }
    g << p;
    return 0;
}