#include <cstdio>
#include <cmath>

using namespace std;

int mod;

int phi(int n) {
    int lim=(int)sqrt((double)n);
    int ans=n;
    int i=2;
    bool ok=false;
    while(n%i==0) {
        n/=i;
        ok=true;
    }
    if(ok) {
        ans/=i;
        ans*=(i-1);
        lim=(int)sqrt((double)n);
    }
    for(int i=3; i*i <= n; i+=2) {
        bool ok=false;
        while(n%i==0) {
            n/=i;
            ok=true;
        }
        if(ok) {
            ans/=i;
            ans*=(i-1);
            lim=(int)sqrt((double)n);
        }
    }
    if(n>1)ans=ans/n*(n-1);
    return ans;
}
int lgput(int n, int p) {
    long long x=n;
    long long power=1;
    for(unsigned int i=0; (1LL<<i)<=p; i++) {
        if(((1<<i)&p))
            power=(power*x)%mod;
        x=(x*x)%mod;
    }
    return power;
}

int main() {
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    int a, n;
    scanf("%d%d", &a, &n);
    mod=n;
    n=phi(n)-1;
    printf("%d\n", lgput(a, n));
    return 0;
}