【特别提醒】

2024-11 的模拟赛均需要文件输入输出。

输入文件后缀名为 .in

输出文件后缀名为 .out

【题目描述】

给定长度为 n 的字符串s。你现在要进行恰好一次操作：

选择 1 ≤ l ≤ r ≤ n ，把 s 的子串 s[l : r] 删去，得到新的串 t 。

你想知道：所有可能的操作最后得到的不同的 t 的个数。

【输入格式】

第一行输入一个整数 n，代表字符串的长度。

第二行输入一个长度为 n 的字符串 s。

【输出格式】

输出一行一个整数，表示答案。

【样例输入】

5
abbab

【样例输出】

11

【数据范围】

对于所有数据， 1 ≤ n ≤ 10^6 ，每个字符都是小写字母。

子任务 1 ( 20% ) : 1 ≤ n ≤ 100 。

子任务 2 ( 20% ) : 1 ≤ n ≤ 500 。

子任务 3 ( 20% )： 1 ≤ n ≤ 4000 。

子任务 4 ( 40% ) : 无特殊限制。