#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

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

#define nmax

#define ll long long

int A, N;

void citeste(){
    f >> A >> N;
}

int put(int a, int b){
    // a ^ b;
    int rez = 1;
    while(b){
        if (b % 2 == 1){
            rez = (rez * a) % N;
        }
        a = (a * a) % N;
        b /= 2;
    }
    return rez;
}

void rezolva(){
    // deci eu vreau sa aflu inversul lui A; adica A * ceva trebuie sa fie congruent cu 1 (modulo n) adica (A * ceva) % n = 1;
    // eu stiu ca [A ^ (n-1)] % n = 1; doar daca n e nr prim; => [A * A^(n-2) ] % n = 1; => ceva = A ^ (n-2);
    g << put(A, N-2) << "\n";
}

int main(){
    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;
}