1
2
3
4
5
int
int
rep(i,2
inv[i] = inv[mod%i]*(mod-mod/i)%mod;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ll extend_gcd
if
if
x = 1
return
}
ll d = extend_gcd(b,a%b,y,x);
y -= a/b*x;
return
}
ll mod_reverse
ll x,y;
ll d = extend_gcd(a,n,x,y);
if
else
}