#include<bits/stdc++.h>

using namespace std;

int a,n,x,y;

long long invers_modular(int a, int b, int& x, int& y) {
    if (b==0) {
        x=1;
        y=0;
        return x;
    }
    int x0,y0;
    invers_modular(b, a%b, x0, y0);
    x=y0;
    y=x0-a/b*y0;
    return x;
}

int main() {
    ifstream cin("inversmodular.in");
    ofstream cout("inversmodular.out");
    cin>>a>>n;

    cout<<(invers_modular(a,n,x,y)+1LL*n)%n;

    return 0;
}