题目描述

给定一个长度为 $N$ 的字符串 $S$，请你计算 $S$ 中有多少个连续子串是回文串。

输入格式

第一行：一个正整数 $N$，表示字符串的长度。

第二行：一个长度为 $N$ 的字符串 $S$。

输出格式

输出一个整数，表示回文子串的个数。

输入输出样例

输入 #1

3
aba

输出 #1

4

输入 #2

2
aa

输出 #2

3

数据规模与约定

• 对于 60% 的数据，$1 \le N \le 100$。
• 对于 100% 的数据，$1 \le N \le 2000$。