Palindrome
题号：NC19786
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

修修在蒜头送给他的奖杯上看到了一个长度为n的字符串s。
他希望从s中选择两个非空子串a,b（可以有重叠的部分），使得它们拼起来是一个回文串。
修修很快就算出了方案数，他听说你也会数数，就让你也来解决一下这个问题。两个方案不同当且仅当a,b中至少一个的长度或位置不同。

输入描述:

第一行一个整数n (1 ≤ n ≤ 2*105)，第二行一个字符串s。保证s只包含小写字母。

输出描述:

输出一行一个整数表示方案数。
示例1

输入

复制 
3
aba

输出

复制 
16
示例2

输入

复制 
10
abbaaababb

输出

复制 
360