#include<cstdio>
int a,n,x=1,y=1;
void init(){
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%d%d",&a,&n);
}
int euclid(int a,int n,int&x,int&y){
    int x0,y0,d;
    if (n==0){
        x=1;
        y=0;
        return a;
    }
    d=euclid(n,a%n,x0,y0);
    x=y0;
    y=x0-(a/n)*y0;
    return d;
}
void print(){
    while(x<0)
        x+=n;
    while(x>n)
        x-=n;
    printf("%d",x);
}
int main(){
    init();
    euclid(a,n,x,y);
    print();
    return 0;
}