int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

#define M 1000000
int marked[M / 64 + 2];
#define on(x) (marked[x / 64] & (1 << (( x % 64) / 2)))
#define mark(x) (marked[x / 64] |= (1 << ((x % 64) / 2)))
using namespace std;
vector<int>primes;
void sieve(void)
{
    for(int i = 3; i * i <= M; i += 2)
    {
        if(!on(i))
        {
            for(int j = i * i; j <= M; j += i + i)
                mark(j);
        }
    }
    primes.push_back(2);
    for(int i = 3; i <= M; i += 2)
    {
        if(!on(i))
            primes.push_back(i);
    }
}
#define N 10000
int ara[N];
void sieve(void)
{
    int i, j;
    for(i = 2; i < N; i++)
        ara[i] = 1;
    for(i = 3; i * i <= N; i+= 2)
    {
        if(ara[i] == 1)
            for(j = i * i ; j <= N; j+=i + i)
            {
                ara[j] = 0;
            }
    }
}
int is_prime(int n)
{
    if(n < 2)
        return 0;
    else if(n == 2)
        return 1;
    else if(n % 2 == 0)
        return 0;
    else
        return ara[n];
}
int inv[SIZE];
inv[1] = 1;
for ( int i = 2; i <= n; i++ ) {
    inv[i] = (-(m/i) * inv[m%i] ) % m;
    inv[i] = inv[i] + m;
}
typedef long long int ll;
ll Bigmod(ll n, ll p, ll m)
{
    if(p == 0)
        return 1;
    if(p % 2 == 0)
    {
        ll ret = Bigmod(n, p / 2, m);
        return ((ret % m) * (ret % m)) % m;
    }
    else
        return ((n % m) * (Bigmod(n, p - 1, m) % m)) % m;
}
typedef long long ll;
ll power(ll a, ll b, ll m)
{
    if(b == 1)
        return a % m;
    if((b & 1) == 1)
        return ( power(a, b-1, m) * a ) % m;
    else
    {
        ll x = power(a, b / 2, m);
        x = (x * x) % m;
        return x;
    }
}
#include<bits/stdc++.h>
#define int long long
#define M 1000000
#define pii pair<int, int>
#define x first
#define y second
#define on(x) (marked[x / 64] & (1 << (( x % 64) / 2)))
#define mark(x) (marked[x / 64] |= (1 << ((x % 64) / 2)))
using namespace std;
int marked[M / 64 + 2];
void sieve(void)
{
    for(int i = 3; i * i <= M; i += 2)
    {
        if(!on(i))
        {
            for(int j = i * i; j <= M; j += i + i)
                mark(j);
        }
    }
}
bool IsPrime(int n)
{
    return n > 1 && ( n == 2 || ((n & 1) && !on(n)));
}
int Bigmod(int n, int p, int m)
{
    if(p == 0)
        return 1;
    if(p % 2 == 0)
    {
        int ret = Bigmod(n, p / 2, m);
        return ((ret % m) * (ret % m)) % m;
    }
    else
        return ((n % m) * (Bigmod(n, p - 1, m) % m)) % m;
}
pii extendedEuclid(int a, int b)
{
    if(b == 0)
        return pii(1, 0);
    else
    {
        pii d = extendedEuclid(b, a % b);
        return pii(d.y, d.x - d.y * (a / b));
    }
}
int ModInverse(int a, int m)
{
    pii ans = extendedEuclid(a, m);
    ans.x %= m;
    if(ans.x < m)
        ans.x += m;
    return ans.x;
}
main()
{
    sieve();
    int a, m;
    cin >> a >> m;
    if(IsPrime(m))
    {
        int x = Bigmod(a, m-2, m);
/// Fermat's little theorem
///  A^(M-1) ≡ 1 (mod M) (Divide both side by A)
/// A^(M-2) ≡ 1/A (mod M)
///  A^(M-2) ≡ A^-1 (mod M)
        cout << x << endl;
    }
    else
        cout << ModInverse(a, m) << endl;
}