CF717A Festival Organization

题意：若一个 01 串长度在 中，且不存在连续 个或更多的 0，则称为好串。

现在要选出 个长度相同的好串，问有几种选法。

答案对 取模，，，时限 。

---

记 为长度为 的好串数目，易知 。答案是 。

考虑差分，只需计算 其中每个 都是线性递推，共 个线性递推点积再求前缀和，仍是线性递推。

暴力算出 的前若干项，用 BM 算法求解递推式（打表可知递推式长度不超过 ），然后求解线性递推的一项，复杂度可以做到 。