【模板】乘法逆元

void exgcd(LL a,LL b,LL &d,LL &x,LL &y) { if(!b) d=a,x=1,y=0; else { exgcd(b,a%b,d,y,x); y-=x*(a/b); } } LL inv(LL u) { LL x,y,d; exgcd(u,mod,d,x,y); return (x%mod+mod)%mod; }