#include #include #include #include #include #define REP(i,a,b) for(i=a;i0){ q=r0/r1; r2=r0%r1; a2=a0-q*a1; b2=b0-q*b1; r0=r1; r1=r2; a0=a1; a1=a2; b0=b1; b1=b2; } *c=r0; *a=a0; *b=b0; } ll get_inv(ll n, ll p){ ll a,b,c; extended_euclid(n,p,&c,&a,&b); if(a