#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
bool isprim(int N) {
    for (long long i = 2; i * i <= N; i++) {
        if (N % i == 0) {
            return false;
        }
    }
    return true;
}
long long gcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    long long Gcd = gcd (b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;

    return Gcd;
}

long long inversulmodular(long long a, long long b) {
    long long x,y;
    long long g = gcd(a, b, x, y);

    if (g != 1) {
        return -1;
    } else {
        return ((x % b) +  b) % b;
    }
}
int main() {
    long long A, N;
    fin >> A >> N;
    if (isprim(N)) {
        // cand N este prim
        // ne trebuie A ^ N-2
        long long baza = A, exp = N-2;
        baza%= N;
        long long r = 1;
        while (exp) {
            if (1 & exp) {
                r = (r * baza) % N;
            }
            baza = baza * baza % N;
            exp >>= 1;
        }
        // r este inversul modular
        fout << r;
    } else {
        // cazul in care n este neprim/compus

        fout << inversulmodular(A, N);
    }


    fin.close();
    fout.close();
    return 0;
}