Rikka 正在为算法协会组织一场新年派对。她邀请了来自 26 个不同组别的 $n$ 名演员，这些组别用小写字母表示。Rikka 想要从中选择一些演员参加开场表演。

现在，这 $n$ 名演员排成一排。第 $i$ 名演员属于 $s_i$ 组。Rikka 决定选择一个非空区间 $[l, r]$ ($1 \le l \le r \le n$)，并让该区间内的所有演员参加开场表演。

Rikka 准备了 26 种不同的动作。假设区间 $[l, r]$ 已经确定，开场表演将按以下方式进行： 演员将按顺序表演。第 $l$ 名演员先表演，第 $r$ 名演员最后表演； 假设现在第 $i$ 名演员即将表演。他/她将按以下方式决定自己的动作： 如果在他/她之前已经有来自 $s_i$ 组的演员 $j$ 表演过，那么第 $i$ 名演员将选择与演员 $j$ 相同的动作。否则，他/她将选择尚未被任何人选过的第一个动作（即编号最小的动作）。

例如，如果选择了来自组别 “abacb” 的 5 名演员，他们将分别选择动作 1, 2, 1, 3, 2。

Rikka 发现不同的区间有时会导致相同的表演。例如，如果有 6 名演员，且他们分别来自 “abacbc”，则区间 $[1, 3]$ 和 $[4, 6]$ 将产生相同的表演。

给定字符串 $s$，Rikka 希望你计算不同可能表演的数量。 两个表演不同，当且仅当它们包含的动作数量不同，或者存在一个索引 $i$，使得这两个表演中第 $i$ 个动作不同； 一个表演是可能的，当且仅当它能由 $s$ 的某个区间 $[l, r]$ 产生。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示演员的数量。 第二行包含一个长度为 $n$ 的小写字符串 $s$。$s_i$ 表示第 $i$ 名演员所属的组别。

输出格式

输出一行，包含一个整数，表示不同可能表演的数量。

样例

输入 1

5
ababc

输出 1

7

输入 2

6
abacbc

输出 2

10

输入 3

11
ababcdcefef

输出 3

33

说明

对于第一个样例，共有 7 种不同的可能表演：

1. 动作 1，对应区间 $[1, 1], [2, 2], [3, 3], [4, 4], [5, 5]$；
2. 动作 1, 2，对应区间 $[1, 2], [2, 3], [3, 4], [4, 5]$；
3. 动作 1, 2, 1，对应区间 $[1, 3], [2, 4]$；
4. 动作 1, 2, 3，对应区间 $[3, 5]$；
5. 动作 1, 2, 1, 2，对应区间 $[1, 4]$；
6. 动作 1, 2, 1, 3，对应区间 $[2, 5]$；
7. 动作 1, 2, 1, 2, 3，对应区间 $[1, 5]$。