| 11 | namespace atcoder { |
| 12 | |
| 13 | long long pow_mod(long long x, long long n, int m) { |
| 14 | assert(0 <= n && 1 <= m); |
| 15 | if (m == 1) return 0; |
| 16 | internal::barrett bt((unsigned int)(m)); |
| 17 | unsigned int r = 1, y = (unsigned int)(internal::safe_mod(x, m)); |
| 18 | while (n) { |
| 19 | if (n & 1) r = bt.mul(r, y); |
| 20 | y = bt.mul(y, y); |
| 21 | n >>= 1; |
| 22 | } |
| 23 | return r; |
| 24 | } |
| 25 | |
| 26 | long long inv_mod(long long x, long long m) { |
| 27 | assert(1 <= m); |