配点 : 100 点
問題文
由小写英文字母组成的长度 N 的字符串 S=S_1 S_2 \dots S_N 存在。以下操作恰好进行 1 次时,请求最后可能出现的 S 字符串种类数。
- 1 \le l \le r \le N 的整数 选择 l, r ,S 可以得到第 l 从第一个字符开始 r 移除到第几个字符为止。也就是说,操作之后 S 是 您也可以写 S_1S_2\dots S_{l-1}S_{r+1}\dots S_N 变为。
制約
- N 是一个整数
- 1 \leq N \leq 5 \times 10^5
- S 是小写字母的长度 N 的字符串
入力
输入是按以下格式从标准输入给出的。
N S
出力
答案 请打印除以 1 行输出。
入力例 1
5 abbab
出力例 1
11
可以得到 S 如下: 11 是的。 请注意,我们正在寻找除以
- 空文字列
aaabababababbabbaabbbbbabbbab
入力例 2
5 aaaaa
出力例 2
5
入力例 3
4 utpc
出力例 3
10