| 186 | init = {s.begin(), s.begin() + m}; |
| 187 | } |
| 188 | ll solve(ll n) { |
| 189 | if (mod == 1) return 0; |
| 190 | if (n < m) return init[n]; |
| 191 | vec v(m), u(m << 1); |
| 192 | ll msk = !!n; |
| 193 | for (ll m = n; m > 1; m >>= 1) msk <<= 1; |
| 194 | v[0] = 1 % mod; |
| 195 | for (ll x = 0; msk; msk >>= 1, x <<= 1) { |
| 196 | fill_n(u.begin(), m * 2, 0); |
| 197 | x |= !!(n & msk); |
| 198 | if (x < m) u[x] = 1 % mod; |
| 199 | else {// can be optimized by fft/ntt |
| 200 | for (int i = 0; i < m; ++i) { |
| 201 | for (int j = 0, t = i + (x & 1); j < m; ++j, ++t) { |
| 202 | u[t] = (u[t] + v[i] * v[j]) % mod; |
| 203 | } |
| 204 | } |
| 205 | for (int i = m * 2 - 1; i >= m; --i) { |
| 206 | for (int j = 0, t = i - m; j < m; ++j, ++t) { |
| 207 | u[t] = (u[t] + trans[j] * u[i]) % mod; |
| 208 | } |
| 209 | } |
| 210 | } |
| 211 | v = {u.begin(), u.begin() + m}; |
| 212 | } |
| 213 | ll ret = 0; |
| 214 | for (int i = 0; i < m; ++i) { |
| 215 | ret = (ret + v[i] * init[i]) % mod; |
| 216 | } |
| 217 | return ret; |
| 218 | } |
| 219 | vec init, trans; |
| 220 | ll mod; |
| 221 | int m; |