#include <cstdio>
using namespace std;

int main()
{
    int a, b, cat[32], x, y, nc, r, i, n;
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    scanf("%d%d", &a, &b);
    n = b;
    nc = 0;
    while(b!=0){
        r = a%b;
        cat[++nc] = a/b;
        a = b;
        b = r;
    }
    x = 1; y = 0;
    for(i=nc; i>=1; i--){
        r = x;
        x = y;
        y = r - cat[i]*y;
    }
    while(x<0)
        x = x + n;
    printf("%d\n", x);

    return 0;
}