#include <bits/stdc++.h>
#define VAL 22
#define MOD 13

using namespace std;

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

int numar, modulo;

int modularInverse(int numar, int modulo); //returneaza inversul modular a lui "numar", mod "modulo"
int expLogaritmica(int numar, int putere, int modulo);
int gcd(int, int);

/*
Folosim teorema lui Fermat:
Daca m este numar prim atunci  a^(-1) congruent a^(m-2) mod "modulo"
Asadar, rezultatul va fi a^(m-2) mod "modulo"
*/

int main(){
    fin >> numar >> modulo;
    fout << modularInverse(numar, modulo) << '\n';
    return 0;
}


int modularInverse(int numar, int modulo){
    if(gcd(numar, modulo) != 1){
        return -1;
        }
        else{
            return expLogaritmica(numar, modulo-2, modulo);
            }
}

int expLogaritmica(int numar, int putere, int modulo){
    long long int val;
    if(putere == 1)
        return numar%modulo;
    if(putere % 2 == 0){
        val = expLogaritmica(numar, putere/2, modulo);
        return (val*val)%modulo;
        }
        else{
            val = expLogaritmica(numar, putere/2, modulo);
            val = (val*val)%modulo;
            val *= numar;
            val %= modulo;
            return val;
            }
}

int gcd(int a, int b){
    if(a % b == 0)
        return b;
        else
        return gcd(b, a%b);
}