在英语课上,尼克根本无事可做,他想起了一个叫做回文的奇妙字符串。我们应该提醒您,如果一个字符串从左到右和从右到左都可以以相同的方式读取,则该字符串称为回文。以下是此类字符串的示例:“eye”、“pop”、“level”、“aba”、“deed”、“racecar”、“rotor”、“madam”。
尼克开始仔细查找他们在课堂上阅读的文本中的所有回文。对于文本中每个回文的出现,他写了一对——该出现在文本中的开头位置和结尾位置。尼克将他在文本中发现的每个回文的每次出现称为“子回文”。当他找到所有的子回文时,他决定找出这些子回文中有多少个不同的对交叉。如果两个子回文覆盖文本中的共同位置,则它们交叉。没有回文可以跨越自身。
让我们以文本 «babb» 为例来看看 Nick 执行的操作。一开始他写出了所有的子回文:
• «b» — 1..1
• «bab» — 1..3
• «a» — 2..2
• «b» — 3..3
• «bb» — 3..4
• «b» — 4..4
然后尼克计算了这些交叉的子回文中不同对的数量。这些对有六对:
1. 1..1 与 1..3 交叉
2. 1..3 与 2..2 交叉
3. 1..3 与 3..3 交叉
4. 1..3 与 3..4 交叉
5. 3..3 与 3..4 交叉
6. 3..4 与 4..4 交叉
由于手动执行所有描述的操作非常累人,尼克请你帮助他编写一个程序,可以找出交叉的不同子回文对的数量。如果两个子回文对中的一个包含子回文而另一个不包含,则这两个子回文对被视为不同。
输入
第一个输入行包含整数 n (1 ≤ n ≤ 2·106) — 文本长度。以下行包含 n 个小写拉丁字母(从 a 到 z)。
输出
在唯一的一行中输出彼此交叉的两个子回文的不同对的数量。输出对 51123987 取模的答案。
示例
输入 #1
4 babb
输出 #1
6
输入 #2
2 aa
输出 #2
2