#include <iostream>
#include <fstream>

using namespace std;

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

int mod, n;

int exp(int n, int p){
        int r = 1;
        while(p) {
                if (p % 2 == 1) r = (n * r) % mod;
                n = (n * n) % mod;
                p /= 2;
        }
        return r;
}

int IE(int n){
        int r = n;
        for(int p = 2; p * p <= n; p++) {
                if(n % p == 0) {
                        while(n % p == 0) n /= p;
                        r -= r / p;
                }
        }
        if(n > 1) r -= r / n;
        return r;
}

inline int invers(int n, int p){
        return exp(n, IE(p) - 1) % p;
}

int main()
{
        ios_base::sync_with_stdio(false);
        in.tie(NULL), out.tie(NULL);

        in >> n >> mod;
        out << invers(n, mod);

        return 0;
}