Palisection

Problem Source

CF 17E

Problem Description

You are given a string $s$ consisting of lowercase letters. Find the number of pairs of palindromic substrings that share at least one common character, and output the answer modulo $51123987$.

Input Format

The first line contains an integer $n$, the length of the string.

The second line contains a string $s$.

Output Format

Output one integer: the answer modulo $51123987$.

Sample Input

4
babb

Sample Output

6

Constraints

For all data, $1 \leq n \leq 2 \times 10^6$, and the string consists of lowercase letters only.