// codesnip-guard: modinv
#[cfg_attr(any(),rustfmt::skip)]#[doc=" Requires 0 < a < m < 2^63 and gcd(a, m) == 1."]pub fn modinv(a:u64,m:u64)->u64{let(mut a,mut b)=(a as i64,m as i64);let(mut u,mut x)=(1,0);while a!=0{let k=b/a;x-=k*u;b-=k*a;std::mem::swap(&mut x,&mut u);std::mem::swap(&mut b,&mut a);}(if x<0{x+m as i64}else{x})as _}
// codesnip-guard: extgcd
#[cfg_attr(any(),rustfmt::skip)]pub fn extgcd(mut a:i64,mut b:i64)->(i64,i64,i64){let(mut u,mut v,mut x,mut y)=(1,0,0,1);while a!=0{let k=b/a;x-=k*u;y-=k*v;b-=k*a;std::mem::swap(&mut x,&mut u);std::mem::swap(&mut y,&mut v);std::mem::swap(&mut b,&mut a);}(b,x,y)}