#include <bits/stdc++.h>
using namespace std;
/// a * x + b * y = cmmdc(a,b)
int cmmdc(int a,int b,int &x,int &y){
    if(b==0){
        x=1;y=0;
        return a;
    }
    int x1,y1;
    int d=cmmdc(b,a%b,x1,y1);
    x=y1;
    y=x1-a/b*y1;
    return d;
}
int InvMod(int A,int N){
    /// cmmdc(A,N) = 1
    /// A * x + N * y = 1
    int inv,trash;
    cmmdc(A,N,inv,trash);
    if(inv<0) inv=inv-N*(inv/N-1);
    else inv=inv%N;
    return inv;
}
int main(){
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    int A,N;
    cin>>A>>N;
    cout<<InvMod(A,N);
}