题目描述

给定一个长度为 $N$ 的字符串 $S$。

对于每个 $1\leq\ i\leq\ N$，令 $S_i$ 表示从 $S$ 中删除第 $i$ 个字符后得到的字符串。 找出满足以下两个条件的整数对 $(i,j)$ 的数量：

1. $1\leq\ i\ <\ j\leq\ N$
2. $S_i\ =\ S_j$

输入格式

一行输入两个整数 $N$ 和 $S$。

输出格式

输出所求答案。

输入输出样例 #1

输入 #1

7
abbbcca

输出 #1

4

输入输出样例 #2

输入 #2

4
xxxx

输出 #2

6

输入输出样例 #3

输入 #3

2
pp

输出 #3

1

输入输出样例 #4

输入 #4

2
st

输出 #4

0

说明/提示

样例 1 解释

以下是按顺序的 $S_i$ 字符串：bbbcca, abbcca, abbcca, abbcca, abbbca, abbbca, abbbcc。

以下 $4$ 对 $(i,j)$ 满足条件：

• $(i,j)=(2,3)$
• $(i,j)=(2,4)$
• $(i,j)=(3,4)$
• $(i,j)=(5,6)$

数据范围

• $2\leq\ N\leq\ 3\times\ 10^5$
• $S$ 是一个由小写英文字母组成的长度为 $N$ 的字符串。