远古 AGC 还是有些挺简单的题的。

首先假设 ，否则将整个串 取反对答案无影响。

那么环上就不可能出现连续两个 ，这启发我们考察连续两个 中间的 连续段长度 。

那么 必须是奇数。因为考察起点两边 的个数，如果两边 的个数的奇偶性都与 中第一段 长度的奇偶性不同，显然无法从起点走到两边的 。当 存在偶数时两边都为偶数或都为奇数，一定存在这种情况。

进一步地也可以推出，设第一段 长度为 ，那么 。

再考虑第二段及以后的限制。因为 是奇数，在 中一段长度为偶数的 显然不会让你从一个 跳到另一个 ，只会原路返回，而一段长度为奇数的 可以让你跳到唯一一个离自己最近的 。也就是说， 中第二段及以后的 段，可以在任意一个在环上的 连续段被走到，所以 必须不超过 中第二段及以后的 段的长度。

容易证明上述三个限制是充要的，据此 DP 即可。设 表示长度为 的链，两端为 的方案数。算答案时枚举第一个 和最后一个 之间 的个数 ，将 累加进答案即可。