#include <bits/stdc++.h>

using namespace std;

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

long long a, n;
const long long MOD=n;

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;
}

long long put(long long a, long long n){
    long long p=1;
    while(n){
        if(n%2){
            p=(p*a)%MOD;
        }
        a=(a*a)%MOD;
        n/=2;
    }
    return p;
}

int main(){
    f >> a >> n;
    int p=phi(n)-1;
    g << put(a, p);
    return 0;
}