#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/i)*(i-1);
        }
    }
    if(a != 1)
        am = (am/a)*(a-1);
    return am;
}

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

int main() {

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

    return 0;
}