P4987 回文项链

**数据已增强，各位不要再交暴力了。** 国庆节期间，哥哥送了小埋一条项链。（假的，日本人过什么国庆。） 然而小埋不太开心，她更想要买一部新手机玩游戏。

不过小埋很快发现了项链的神奇之处。 我们把项链看作一个$n$元环，记作$s$，环上每个结点由大写'A'-'Z'中的一个字母组成。小埋惊奇的发现，环上有很多回文串！我们定义回文串为环上一个首尾不重叠的连续子串（即环上每个结点最多被使用一次），且满足**存在一个回文中心**$i$，使得$i$之前的若干个字符分别与其关于$i$中心对称的字符相同。 现在，小埋给出你这个环，并希望知道有多少长度为$l$的本质不同的回文串；我们认为两个回文串本质不同，当且仅当它们回文中心所在结点不同。

无

无

**本题每个测试点时限500ms** 对于$30$%的数据，$n