#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");

int lgput(int a, int b, int mod)
{
    if(b == 1)
        return a % mod;
    if(b == 0)
        return 1;
    int rez = lgput(a, b/2, mod) % mod;
    if(b % 2 == 0)
        return (1LL * rez * rez) % mod;
    else
        return (1LL * (1LL * rez * rez) % mod) * a % mod;
}

int phi(int n) {
    int ret = n;
    for(int i = 2; i * i <= n; i++) {
        int expon = 0;
        while(n % i == 0) {
            ++ expon;
            n /= i;
        }
        if(n % i == 0)
            ret = (ret / i) * (i - 1);
    }
    if(n != 1)
        ret = (ret / n) * (n - 1);
    return ret;
}

int main()
{
    int a, n;
    in >> a >> n;
    out << lgput(a, phi(n) - 1, n);
    return 0;
}