#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
long long eul(long long n) {
        long long r = n,d = 2;
        while(n > 1) {
                if (n % d == 0) {
                        r = r/d * (d-1);
                }
                while(n%d == 0) n/=d;
                d++;
                if (d * d > n) d = n;
        }
        return r;
}
long long mod;
long long lgpow(long long a,long long n) {
        long long p = 1;
        for (int k = 1;k<=n;k<<=1) {
                if (n & k) {
                        p*=a;
                        p=p%mod;
                }
                a*=a;
                a=a%mod;
        }
        return p % mod;
}
int main() {
        long long a,n;
        fin>>a>>n;
        long long phi = eul(n) - 1;
        mod = n;
        fout<<lgpow(a,phi)<<"\n";
        return 0;
}