Palisection

题目来源

CF 17E

题目描述

给你一个字符串 $s$，字符串由小写字母组成，现在你需要求出 $s$ 中有多少对有公共部分的回文子串，请输出答案 mod $51123987$。

输入格式

第一行一个整数 $n$ 表示字符串的长度。

第二行一个字符串 $s$。

输出格式

输出一个整数表示答案 mod $51123987$。

样例输入

4
babb

样例输出

6

数据范围

对于所有数据，保证 $1\leq n \leq 2 \times 10^6$， 字符串均由小写字母构成。