#include <bits/stdc++.h>
#define t long long
t x,y,a,n,q;void e(t a,t b){if(!b){x=1,y=0;return;}e(b,a%b),q=y,y=x-(a/b)*y,x=q;}main(){std::ifstream("inversmodular.in")>>a>>n;e(a,n);while(x<0)x+=n;std::ofstream("inversmodular.out")<<x;}