#include <bits/stdc++.h>
void nos()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}
namespace BasicMath{

    //Euler fuction in O(sqrt(n))
    int phi(int n)
    {
        if(n == 1)
            return 0;
        int result = n;
        for (int i=2; i*i<=n; ++i)
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
        if (n > 1)
        result -= result / n;
        return result;
    }
    //Divisors
    std::vector < std::pair < int ,int > > Divisors(int n)
    {
        //{baza, exponent}
        std::vector < std::pair< int , int> > ans;
        if(n % 2 == 0)
        {
            int exp = 0;
            while(n % 2 == 0)
            {
                n /= 2;
                ++exp;
            }
            ans.push_back({2,exp});
        }
        int d = 3;
        while(n!=1)
        {
            if(n % d == 0)
            {
                int exp = 0;
                while(n % d == 0)
                {
                    n /= d;
                    exp++;
                }
                ans.push_back({d,exp});
            }
            if(d * d > n)
                break;
            d+=2;
        }
        if(n != 1)
            ans.push_back({n,1});

        return ans;
    }
    int fastpowsimple(int base,int exp,int MOD)
    {
        int ans = 1;
        while(exp)
        {
            if(exp & 1)
                ans*=base,ans%=MOD;
            base *= base;
            base %= MOD;
            exp >>= 1;
        }
        return ans;
    }
    int gcd(int a,int b)
    {
        while(b)
        {
            a %= b;
            std::swap(a,b);
        }
        return a;
    }
    int ExtendedEuclid(int a, int b, int &x, int &y)
    {
        //a*x + b*y = (gcd(a,b))
        if(a == 0)
        {
            x = 0; y = 1;
            return b;
        }
        int x1,y1;
        int d = ExtendedEuclid(b%a,a,x1,y1);
        x = y1 - (b / a) * x1;
        y = x1;
        return d;
    }
    void NormaliseMOD(int &x, int MOD)
    {
        if(x < 0)
        {
            int amount = (-x)/MOD + 1;
            x += amount * MOD;
        }
        x %= MOD;
    }
    int ModularInverse(int n, int MOD)
    {
        int x,y;
        int g = ExtendedEuclid(n,MOD,x,y);
        if(g!=1)
        {
            std::cout<<"Input not Correct";
            return -1;   
        }
        NormaliseMOD(x,MOD);
        return x;
    }
}

std::ifstream f("inversmodular.in");
std::ofstream g("inversmodular.out");
int32_t main()
{
    int a,MOD;
    f>>a>>MOD;
    g<<BasicMath::ModularInverse(a,MOD);
}