该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

如果交换字符之间的出现顺序若干（ $\ge0$ ）次后，一个字符串能够变为一个回文串，就称为准回文串。

给定一个由英文字母构成的字符串，求准回文子串的数量。

Format

Input

第一行输入一个正整数 $n(\le10^6)$ 。

第二行输入一个长度为 n 的字符串，且保证仅包含字母。

Output

一个整数，表示准回文子串的数量。

Samples

7
ABADABA

12

Limitation

1s, 1024KiB for each test case.