CF17E.Palisection

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

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..11..1 • «bab» — 1..31..3 • «a» — 2..22..2 • «b» — 3..33..3 • «bb» — 3..43..4 • «b» — 4..44..4 Then Nick counted the amount of different pairs among these subpalindromes that cross. These pairs were six:

  1. 1..11..1 cross with 1..31..3 2. 1..31..3 cross with 2..22..2 3. 1..31..3 cross with 3..33..3 4. 1..31..3 cross with 3..43..4 5. 3..33..3 cross with 3..43..4 6. 3..43..4 cross with 4..44..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.

输入格式

The first input line contains integer nn ( 1<=n<=21061<=n<=2·10^{6} ) — length of the text. The following line contains nn lower-case Latin letters (from a to z).

输出格式

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

输入输出样例

  • 输入#1

    4
    babb
    

    输出#1

    6
    
  • 输入#2

    2
    aa
    

    输出#2

    2
    
首页