#include<fstream.h>   
#include <iostream.h>    
 int a,n,x,y,d;
void euclid(int a,int b,int &x,int &y,int &d)   
{   
    if(b==0)   
    {   
        x=1;   
        y=0;   
        d=a;   
        return;   
    }   
    int x2,y2;   
    euclid(b,a%b,x2,y2,d);   
    x=y2;   
    y=x2-a/b*y2;   
}   
int main()   
{   
    ifstream f("inversmodular.in");   
    ofstream g("inversmodular.out");     
    f>>a>>n;   
    f.close();
    euclid(a,n,x,y,d);   
    if(x%n<0)   
        g<<x%n+n;   
    else g<<x%n;   
    g.close();
    return 0;   
}