如果一个字符串可以被拆分为 $AABB$ 的形式，其中 $A$ 和 $B$ 是任意非空字符串，则我们称该字符串的这种拆分是优秀的。一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。

现在给出一个长度为 $n$ 的字符串 $S$ ，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。这里的子串是指字符串中连续的一段。

以下事项需要注意：

• 出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被记入答案。
• 在一个拆分中，允许出现 $A = B$。例如 $cccc$ 存在拆分 $A = B = c$。
• 字符串本身也是它的一个子串。

加里敦大学的生物研究所发现了决定人喜不喜欢吃藕的基因序列 $S$ ,有这个序列的碱基序列就会表现出喜欢吃藕的性状，但是研究人员发现对碱基序列 $S$ ,任意修改其中不超过 $3$ 个碱基，依然能够表现出吃藕的性状。现在研究人员想知道这个基因在 DNA 链 $S0$ 上的位置。所以你需要统计在一个表现出吃藕性状的人的 DNA 序列 $S0$ 上，有多少个连续子串可能是该基因，即有多少个 $S0$ 的连续子串修改小于等于三个字母能够变成 $S$ 。

Aho–Corasick算法，常叫做AC自动机。是一种字符串多模式串匹配算法。能在线性时间内完成多个模式串对一个查询串的匹配。

能自动AC哦。

给定一个字符串 $S$ ，求出 $num$ 数组——对于字符串 $S$ 的前 $i$ 个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作 $num[i]$ 。

特别地，为了避免大量的输出，你不需要输出 $num[i]$ 分别是多少，你只需要输出所有 $(num[i]+1)$ 的乘积，对 $10^9+7$ 取模的结果即可。