CF17E.Palisection

In an English class Nick had nothing to do at all, and remembered about wonderful strings called palindromes. We should remind you that a string is called a palindrome if it can be read the same way both from left to right and from right to left. Here are examples of such strings: «eye», «pop», «level», «aba», «deed», «racecar», «rotor», «madam».

Nick started to look carefully for all palindromes in the text that they were reading in the class. For each occurrence of each palindrome in the text he wrote a pair — the position of the beginning and the position of the ending of this occurrence in the text. Nick called each occurrence of each palindrome he found in the text subpalindrome. When he found all the subpalindromes, he decided to find out how many different pairs among these subpalindromes cross. Two subpalindromes cross if they cover common positions in the text. No palindrome can cross itself.

Let's look at the actions, performed by Nick, by the example of text «babb». At first he wrote out all subpalindromes:

• «b» — 1..1

• «bab» — 1..3

• «a» — 2..2

• «b» — 3..3

• «bb» — 3..4

• «b» — 4..4

Then Nick counted the amount of different pairs among these subpalindromes that cross. These pairs were six:

1. 1..1 cross with 1..3

2. 1..3 cross with 2..2

3. 1..3 cross with 3..3

4. 1..3 cross with 3..4

5. 3..3 cross with 3..4

6. 3..4 cross with 4..4

Since it's very exhausting to perform all the described actions manually, Nick asked you to help him and write a program that can find out the amount of different subpalindrome pairs that cross. Two subpalindrome pairs are regarded as different if one of the pairs contains a subpalindrome that the other does not.

在英语课上，尼克百无聊赖，忽然想起了被称为“回文”的美妙字符串。需要提醒的是：若一个字符串从左到右读与从右到左读完全相同，则称其为回文。以下是一些回文的例子：«eye»、«pop»、«level»、«aba»、«deed»、«racecar»、«rotor»、«madam»。

尼克开始仔细地在课堂所读文本中寻找所有回文。对文本中每个回文的每次出现，他都记录下该次出现的起始位置和结束位置（均以 1 为起始索引）。尼克将他在文本中找到的每个回文的每次出现称为一个子回文（subpalindrome）。当他找出所有子回文后，便决定统计其中有多少对不同的子回文是相交的。若两个子回文在文本中覆盖了至少一个公共位置，则称它们相交。注意：一个回文不能与自身相交。

我们通过文本 «babb» 的例子来说明尼克的操作过程。首先，他列出了所有子回文：

• «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 相交

由于手动执行上述全部操作十分繁琐，尼克请你帮忙编写一个程序，用以计算相交的不同子回文对的总数。若某一对子回文包含一个另一对中没有的子回文，则认为这两对子回文是不同的。

The first input line contains integer n (1 ≤ n ≤ 2·106) — length of the text. The following line contains n lower-case Latin letters (from a to z).

第一行输入包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^6$）—— 文本的长度。接下来的一行包含 $n$ 个小写拉丁字母（从 a 到 z）。

In the only line output the amount of different pairs of two subpalindromes that cross each other. Output the answer modulo 51123987.

在唯一的一行中输出相互交叉的两个子回文串的不同对数。答案对 51123987 取模。