#include <bits/stdc++.h>

#define type long long int

using namespace std;

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

type number, modulo, power = 1, inversModular;

type risingPower(type base, type exponent){
    type product = 1;
    for ( ; exponent; exponent >>= 1 ){
        if ( exponent % 2 )
            product = (product * base) % modulo;
        base = (base*base) % modulo;
    }
    return product;
}

int main(){
    fin >> number >> modulo;

    if ( __gcd(modulo, 1LL) == 1 )
        inversModular = risingPower(number, modulo-2);
    else{
        for ( int index = 2; index*index <= modulo; index++ ){
            if ( modulo % index == 0 ){
                power *= (index-1);
                while ( modulo % index == 0 ){
                    power *= index;
                    modulo /= index;
                }
                power /= index;
            }
        }
        inversModular = risingPower(number, power-1);
    }
    fout << inversModular;
}