#define ll long longvoid exgcd(ll a, ll b, ll &d, ll &x, ll &y) { if(!b) {x = 1, y = 0, d = a; return ;} exgcd(b, a%b, d, y, x); y -= a/b*x;}