Mod

 1func powMod(a, n, M int) int {
 2	r := 1
 3	for n > 0 {
 4		if n&1 == 1 {
 5			r = r * a % M
 6		}
 7		a = a * a % M
 8		n >>= 1
 9	}
10	return r
11}
12
13func invMod(a, M int) int {
14	p, x, u := M, 1, 0
15	for p != 0 {
16		t := a / p
17		a, p = p, a-t*p
18		x, u = u, x-t*u
19	}
20	if x < 0 {
21		x += M
22	}
23	return x
24}
25