{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eIn an English class Nick had nothing to do at all, and remembered about wonderful strings called \u003cspan class\u003d\"tex-font-style-underline\"\u003epalindromes\u003c/span\u003e. 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: «\u003cspan class\u003d\"tex-font-style-tt\"\u003eeye\u003c/span\u003e», «\u003cspan class\u003d\"tex-font-style-tt\"\u003epop\u003c/span\u003e», «\u003cspan class\u003d\"tex-font-style-tt\"\u003elevel\u003c/span\u003e», «\u003cspan class\u003d\"tex-font-style-tt\"\u003eaba\u003c/span\u003e», «\u003cspan class\u003d\"tex-font-style-tt\"\u003edeed\u003c/span\u003e», «\u003cspan class\u003d\"tex-font-style-tt\"\u003eracecar\u003c/span\u003e», «\u003cspan class\u003d\"tex-font-style-tt\"\u003erotor\u003c/span\u003e», «\u003cspan class\u003d\"tex-font-style-tt\"\u003emadam\u003c/span\u003e». \u003c/p\u003e\u003cp\u003eNick 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 \u003cspan class\u003d\"tex-font-style-underline\"\u003esubpalindrome\u003c/span\u003e. 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.\u003c/p\u003e\u003cp\u003eLet\u0027s look at the actions, performed by Nick, by the example of text «\u003cspan class\u003d\"tex-font-style-tt\"\u003ebabb\u003c/span\u003e». At first he wrote out all subpalindromes:\u003c/p\u003e\u003ccenter\u003e• «\u003cspan class\u003d\"tex-font-style-tt\"\u003eb\u003c/span\u003e» — \u003cspan class\u003d\"tex-span\"\u003e1..1\u003c/span\u003e \u003c/center\u003e\u003ccenter\u003e• «\u003cspan class\u003d\"tex-font-style-tt\"\u003ebab\u003c/span\u003e» — \u003cspan class\u003d\"tex-span\"\u003e1..3\u003c/span\u003e \u003c/center\u003e\u003ccenter\u003e• «\u003cspan class\u003d\"tex-font-style-tt\"\u003ea\u003c/span\u003e» — \u003cspan class\u003d\"tex-span\"\u003e2..2\u003c/span\u003e \u003c/center\u003e\u003ccenter\u003e• «\u003cspan class\u003d\"tex-font-style-tt\"\u003eb\u003c/span\u003e» — \u003cspan class\u003d\"tex-span\"\u003e3..3\u003c/span\u003e \u003c/center\u003e\u003ccenter\u003e• «\u003cspan class\u003d\"tex-font-style-tt\"\u003ebb\u003c/span\u003e» — \u003cspan class\u003d\"tex-span\"\u003e3..4\u003c/span\u003e \u003c/center\u003e\u003ccenter\u003e• «\u003cspan class\u003d\"tex-font-style-tt\"\u003eb\u003c/span\u003e» — \u003cspan class\u003d\"tex-span\"\u003e4..4\u003c/span\u003e \u003c/center\u003e\u003cp\u003eThen Nick counted the amount of different pairs among these subpalindromes that cross. These pairs were six:\u003c/p\u003e\u003ccenter\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e1.\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e1..1\u003c/span\u003e cross with \u003cspan class\u003d\"tex-span\"\u003e1..3\u003c/span\u003e \u003c/center\u003e\u003ccenter\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e2.\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e1..3\u003c/span\u003e cross with \u003cspan class\u003d\"tex-span\"\u003e2..2\u003c/span\u003e \u003c/center\u003e\u003ccenter\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e3.\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e1..3\u003c/span\u003e cross with \u003cspan class\u003d\"tex-span\"\u003e3..3\u003c/span\u003e \u003c/center\u003e\u003ccenter\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e4.\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e1..3\u003c/span\u003e cross with \u003cspan class\u003d\"tex-span\"\u003e3..4\u003c/span\u003e \u003c/center\u003e\u003ccenter\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e5.\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e3..3\u003c/span\u003e cross with \u003cspan class\u003d\"tex-span\"\u003e3..4\u003c/span\u003e \u003c/center\u003e\u003ccenter\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e6.\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e3..4\u003c/span\u003e cross with \u003cspan class\u003d\"tex-span\"\u003e4..4\u003c/span\u003e \u003c/center\u003e\u003cp\u003eSince it\u0027s 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.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first input line contains integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 2·10\u003csup class\u003d\"upper-index\"\u003e6\u003c/sup\u003e\u003c/span\u003e) — length of the text. The following line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e lower-case Latin letters (from \u003cspan class\u003d\"tex-font-style-tt\"\u003ea\u003c/span\u003e to \u003cspan class\u003d\"tex-font-style-tt\"\u003ez\u003c/span\u003e).\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eIn the only line output the amount of different pairs of two subpalindromes that cross each other. Output the answer modulo \u003cspan class\u003d\"tex-span\"\u003e51123987\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\nbabb\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\naa\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}