给定一个长度为 $N$ 的字符串 $S = S_1S_2 \dots S_N$，其中包含小写英文字母。请确定通过恰好执行一次以下操作可以得到的不同字符串的数量：

• 选择整数 $l$ 和 $r$，使得 $1 \le l \le r \le N$，并删除 $S$ 中从第 $l$ 个字符到第 $r$ 个字符的子串。得到的字符串为 $S_1S_2 \dots S_{l-1}S_{r+1} \dots S_N$。

输入格式

输入通过标准输入按以下格式提供：

$N$ $S$

• $N$ 是一个整数。
• $1 \le N \le 5 \times 10^5$
• $S$ 是一个长度为 $N$ 的字符串，由小写英文字母组成。

输出格式

在一行中打印答案。

样例

输入格式 1

5
abbab

输出格式 1

11

输入格式 2

5
aaaaa

输出格式 2

5

输入格式 3

4
utpc

输出格式 3

10

说明

在第一个样例中，可能的生成字符串共有以下 11 种：

• 空字符串
• a
• aab
• ab
• abab
• abb
• abba
• abbb
• b
• bab
• bbab