给定一个字符串 $$$s$$$,长度为 $$$n$$$,仅由小写拉丁字母组成。
字符串的子字符串是该字符串的连续子序列。因此,字符串“forces”是字符串“codeforces”的子字符串,但字符串“coder”不是。
您的任务是计算从该字符串中精确删除一个子字符串的方法数,以使所有剩余字符都相等(不同字符的数量为零或一)。
保证$$$s$$$中至少有两个不同的字符。
请注意,您可以删除整个字符串,这是正确的。另请注意,您应该删除至少一个字符。
由于答案可能相当大(但不是很大),请打印它对 $$$998244353$$$ 取模。
如果您是 Python 程序员,请在提交代码时考虑使用 PyPy 而不是 Python。
输入
输入的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 字符串 $$$s$$$ 的长度。
输入的第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$,仅由小写拉丁字母组成。
保证$$$s$$$中至少有两个不同的字符。
输出
打印一个整数 — 以 $$$998244353$$$ 为模从 $$$s$$$ 中删除一个子字符串的方式数,这样所有剩余的字符都相等。
示例
输入 #1
4 abaa
输出 #1
6
输入 #2
7 aacdeee
输出 #2
6
输入 #3
2 az
输出 #3
3
注意
让 $$$s[l; r]$$$ 是 $$$s$$$ 从位置 $$$l$$$ 到位置 $$$r$$$(含)的子串。
然后在第一个示例中您可以删除以下子字符串:
- $$$s[1; 2]$$$;
- $$$s[1; 3]$$$;
- $$$s[1; 4]$$$;
- $$$s[2; 2]$$$;
- $$$s[2; 3]$$$;
- $$$s[2; 4]$$$。
在第二个示例中,您可以删除以下子字符串:
- $$$s[1; 4]$$$;
- $$$s[1; 5]$$$;
- $$$s[1; 6]$$$;
- $$$s[1; 7]$$$;
- $$$s[2; 7]$$$;
- $$$s[3; 7]$$$。
在第三个示例中,您可以删除以下子字符串:
- $$$s[1; 1]$$$;
- $$$s[1; 2]$$$;
- $$$s[2; 2]$$$。