CF17E Palisection

给定一个长度为 $n$ 的小写字母串 $S$，求有多少对相交的回文子串（包含也算相交）。

第一行是字符串长度 $n$($1\le n\le2\times10^6$)。 第二行是字符串 $S$。

相交的回文子串个数，对 $51123987$ 取模。