#include<fstream>
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
int A,N;
int X(int a,int n){
    int S[4],A[4];
    S[1]=a;S[2]=n;
    A[1]=1;A[2]=0;
    while(S[2]){
        S[3]=S[1]%S[2];
        A[3]=A[1]-(S[1]/S[2])*A[2];
        S[1]=S[2];S[2]=S[3];
        A[1]=A[2];A[2]=A[3];
    }
    while(A[1]<0) A[1]+=n;
    return A[1];
}
int main(){
    in>>A>>N;
    out<<X(A,N)<<'\n';
    return 0;
}