/* Invers modular a lui A in raport cu N cand N e prim.
N = MOD
inv(A) = A^(MOD-2); // lgput(A, MOD-2)
Complexitate O(logMOD)
*/

#include <fstream>

using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");


int A, N, inv;

long long lgput(long long n, long long k, long long MOD)
{
    long long m=1;
    while (k!=1)
    {
        if (k%2==0)
        {
            n=(n*n)%MOD;
            k=k/2;
        }
        else
        {
            m=(m*n)%MOD;
            --k;
        }
    }
    return (n*m)%MOD;
}

int invers(int A, int N) {
    return lgput(A, N - 2, N);
}
int main() {
    f >> A >> N;
    inv = invers(A, N);
    g << inv << '\n';

    f.close();
    g.close();
    return 0;
}