#include <bits/stdc++.h>

using namespace std;

ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");

int lgpow(long long p,long long e,long long mod) {
    int res=1;
    while(e) {
        if(e%2==1) {
            res=(res*p)%mod;
        }
        p=(p*p)%mod;
        e/=2;
    }
    return res;
}

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

signed main() {
    int a,n;
    fin>>a>>n;
    fout<<lgpow(a,phi(n)-1,n);
    return 0;
}