#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;
    }
    for(int i=0;i<m;i++)
    {
        if(b*i%m==1)
        {
            cout<<i;
            break;
        }
    }


    return 0;
}