E. Палисечение
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
128 megabytes
ввод
stdin
вывод
stdout

На уроке английского языка Никите совсем нечем было заняться, и он вспомнил о замечательных строках под названием палиндромы. Напомним, что строка называется палиндромом, если она читается одинаково слева направо и справа налево. Примеры таких строк: «eye», «pop», «level», «aba», «deed», «racecar», «rotor», «madam».

Никита стал старательно искать все палиндромы в тексте, который они читали в тот момент на уроке. Для каждого вхождения каждого палиндрома он выписывал пару — позицию начала и позицию конца этого вхождения палиндрома в текст. Каждое вхождение каждого палиндрома Никита называет подпалиндромом. Когда Никита нашел все подпалиндромы, ему стало интересно, сколько различных пар из них пересекается. Два подпалиндрома пересекаются, если они содержат общую позицию в тексте, причем считается, что никакой палиндром не пересекается сам с собой.

Рассмотрим на примере текста «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

Так как это всё изнурительно тяжело делать вручную, Никита попросил вас помочь ему и разработать программу, которая по заданному тексту будет определять количество различных пар пересекающихся подпалиндромов. Две пары подпалиндромов называются различными, если есть подпалиндром, который входит в одну из них и не входит в другую.

Входные данные

В первой строке входных данных содержится целое число n (1 ≤ n ≤ 2·106) — длина текста. На следующей строке будет содержаться ровно n строчных букв латинского алфавита (от a до z).

Выходные данные

В единственной строке выходных данных должно содержаться количество различных неупорядоченных пар пересекающихся подпалиндромов. Ответ нужно выводить по модулю 51123987.

Примеры
Входные данные
4
babb
Выходные данные
6
Входные данные
2
aa
Выходные данные
2