#include <iostream>
#include <cmath>
#include <fstream>
#define int long long
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

using namespace std;

int prim(int a)
{
    if(a==0 || a==1)
        return 0;
    else if(a==2)
        return 1;
    for(int i=3; i<=sqrt(a); i+=2)
    {
        if(a%i==0)
            return 0;
    }
    return 1;
}

int32_t main()
{
    ifstream cin("inversmodular.in");
    ofstream cout("inversmodular.out");
    int b,m,rez=1,n;
    cin>>b>>m;
    n=m;

    if(prim(m)==1)
    {
        //cout<<"L";
        ///b^m-2
        m-=2;
        while(m>0)
        {
            if(m%2==1)
                rez=(rez*b)%n;
            b=(b*b)%n;
            m/=2;
        }
        cout<<rez;
        return 0;
    }

    if(b<=m/2)
    {
        for(int i=m/2; i<m; i++)
        {
            if(b*i%m==1)
            {
                ///daca b<m/2, i trebuie mai mare ca m/2 si invers
                cout<<i;
                break;
            }
        }
    }
    else
    {
        for(int i=0; i<m/2; i++)
        {
            if(b*i%m==1)
            {
                ///daca b<m/2, i trebuie mai mare ca m/2 si invers
                cout<<i;
                break;
            }
        }
    }

    return 0;
}