#include <iostream>
#include <fstream>

using namespace std;

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

int phi(int a) {
    int am = a;
    if(a%2 == 0) {
        while(a%2 == 0)
            a /= 2;
        am /= 2;
    }
    for(int i = 3; i*i <= a; i += 2) {
        if(a%i == 0) {
            while(a%i == 0)
                a /= i;
            am = am - am/i;
        }
    }
    if(a != 1)
        am = am - am/a;
    return am;
}

int lgput(int a, int b, int mod) {
    long long sol = 1;
    for(int i = 1; i <= b; i <<= 1) {
        if((b&i) > 0)
            sol = (1LL*sol*a)%mod;
        a = (1LL*a*a)%mod;
    }
    return sol;
}

/*long long lgput2(int a, int b, int i, int mod) {

    if(b == 1)
        return a;
    if(b == 2)
        return (1LL*a*a)%mod;

    if(b%2 == 0) {
        long long temp = lgput2(a, b/2, i, mod)%mod;
        //cout << a << " " << b << " " << i << " " << temp << '\n';
        return (1LL*temp*temp)%mod;
    } else {
        return (1LL*a*lgput2(a, b-1, i, mod))%mod;
    }

}*/

int main() {

    int a,n,inv,y;
    in >> a >> n;
    out << lgput(a, phi(n)-1, n);

    return 0;
}