| 11 | return ans; |
| 12 | } |
| 13 | void precompute(int len) { |
| 14 | lim = wn[0] = 1; int s = -1; |
| 15 | while (lim < len) lim <<= 1, ++s; |
| 16 | for (int i = 0; i < lim; ++i) rev[i] = rev[i >> 1] >> 1 | (i & 1) << s; |
| 17 | const int g = POW(root, (mod - 1) / lim); |
| 18 | inv_lim = POW(lim, mod - 2); |
| 19 | for (int i = 1; i < lim; ++i) wn[i] = (long long) wn[i - 1] * g % mod; |
| 20 | } |
| 21 | void ntt(vector<int> &a, int typ) { |
| 22 | for (int i = 0; i < lim; ++i) if (i < rev[i]) swap(a[i], a[rev[i]]); |
| 23 | for (int i = 1; i < lim; i <<= 1) { |