CF1096B.Substring Removal

You are given a string $s$ of length $n$ consisting only of lowercase Latin letters.

A substring of a string is a contiguous subsequence of that string. So, string "forces" is substring of string "codeforces", but string "coder" is not.

Your task is to calculate the number of ways to remove exactly one substring from this string in such a way that all remaining characters are equal (the number of distinct characters either zero or one).

It is guaranteed that there is at least two different characters in $s$.

Note that you can remove the whole string and it is correct. Also note that you should remove at least one character.

Since the answer can be rather large (not very large though) print it modulo $998244353$.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.

给你一个长度为 $n$ 的字符串 $s$，其中仅包含小写拉丁字母。

字符串的子串是指该字符串的一个连续子序列。例如，“forces” 是 “codeforces” 的子串，但 “coder” 不是。

你的任务是计算：从该字符串中恰好移除一个子串（即一段连续的字符），使得剩余的所有字符都相等（即剩余字符中不同字符的种类数为 $0$ 或 $1$）的方案数。

保证字符串 $s$ 中至少包含两种不同的字符。

注意：你可以移除整个字符串，这是合法操作；同时，你必须至少移除一个字符。

由于答案可能较大（尽管并非极大），请将结果对 $998244353$ 取模后输出。

如果你使用 Python 编程，请在提交代码时考虑使用 PyPy 而非标准 Python。

The first line of the input contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of the string $s$.

The second line of the input contains the string $s$ of length $n$ consisting only of lowercase Latin letters.

It is guaranteed that there is at least two different characters in $s$.

输入的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）—— 字符串 $s$ 的长度。

输入的第二行包含一个长度为 $n$ 的字符串 $s$，该字符串仅由小写拉丁字母组成。

保证字符串 $s$ 中至少包含两个不同的字符。

Print one integer — the number of ways modulo $998244353$ to remove exactly one substring from $s$ in such way that all remaining characters are equal.

输出一个整数——即从字符串 $s$ 中恰好移除一个子串，使得剩余所有字符都相等的方案数，对 $998244353$ 取模。

Let $s[l; r]$ be the substring of $s$ from the position $l$ to the position $r$ inclusive.

Then in the first example you can remove the following substrings:

• $s[1; 2]$;
• $s[1; 3]$;
• $s[1; 4]$;
• $s[2; 2]$;
• $s[2; 3]$;
• $s[2; 4]$.

In the second example you can remove the following substrings:

• $s[1; 4]$;
• $s[1; 5]$;
• $s[1; 6]$;
• $s[1; 7]$;
• $s[2; 7]$;
• $s[3; 7]$.

In the third example you can remove the following substrings:

• $s[1; 1]$;
• $s[1; 2]$;
• $s[2; 2]$.

令 $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]$。