#include <fstream>
using namespace std;
ifstream f ("inversmodular.in");
ofstream g ("inversmodular.out");
int a,ma;
void usu(int a,int b,int &x,int &y)
{
    int x1,y1;
    if(!b) {x=1;y=0;return;}
    usu(b,a%b,x1,y1);
    x=y1;
    y=x1-y1*(a/b);
}
int invers(int a)
{
    int x,y;
    usu(a,ma,x,y);
    if(x<=0) x=ma+x%ma;
    return x;
}
int main()
{
    f>>a>>ma;
    g<<invers(a);
    return 0;
}