#include <fstream>
#include<bits/stdc++.h>
#define cin fin
#define cout fout
using namespace std;
ifstream cin ("inversmodular.in");
ofstream cout ("inversmodular.out");
int val,MOD,x,y;
void invers(int &x,int &y,int a,int b)
{
    if(b==0)
    {
        x=1;
        y=0;
    }
    else
    {
        invers(x,y,b,a%b);
        int aux=x;
        x=y;
        y=aux-y*(a/b);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>val>>MOD;
    invers(x,y,val,MOD);
    while(x<0)
        x+=MOD;
    cout<<x;
    return 0;
}