// We want to find the integer x such that a * x and 1 are congruent modulo m
// We will use Euler's Theorem: a^(phi(m)) is conguruent with 1 (mod m)
// So x will be a^(phi(m)-1)
// The inverse modular exists if and only if a and m are coprime
/// Complexity: O(sqrtN + logN)

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

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

// Fast exponentiation function;  Complexity: O(logN)
int_fast32_t fexp(int_fast32_t b, const int_fast32_t& e, const int_fast32_t& mod)
{
    int_fast32_t n = 1;
    for(int_fast32_t i = 1; i <= e; i <<= 1)
    {
        if(e & i) n = n * b % mod;
        b = b * b % mod;
    }
    return n;
}


// Modified Erathostenes sieve function (calculates smallest prime factor of each number)
void erathostenes(const int_fast32_t& n, vector<int_fast32_t>& sieve)
{
    for(int_fast32_t i=2, j; i <= n; i++)
    {
        if(sieve[i] == -1)
        {
            sieve[i]= i;
            for(j=i*i; j <= n; j += i) sieve[j] = i;
        }
    }
}

// Euler's Totient function
int_fast32_t totient(const int_fast32_t& n)
{
    vector<int_fast32_t> sieve(n+1, -1), phi(n+1, 1);
    erathostenes(n, sieve);
    for(int_fast32_t i=2, j, p; i <= n; i++)
    {
        p = sieve[i], j = i;
        while(!(j%p))
        {
            phi[i] *= p;
            j /= p;
        }
        phi[i] = (phi[i]/p) * (p-1) * phi[j];
    }
    return phi[n];
}

// Base Modular multiplicative inverse function
int_fast32_t invmod(const int_fast32_t& nr, const int_fast32_t& mod)
{
    if(__gcd(nr, mod) != 1) return 0;
    else return fexp(nr, totient(mod)-1, mod);
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);
    int_fast32_t a, m;
    fin >> a >> m;
    fout << invmod(a, m);
}