Substring Removal
Contest: Educational Codeforces Round 57 (Rated for Div. 2)
Difficulty rating: 1300
Tags: combinatorics, math, strings

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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]$$$.

Example input:
4
abaa

Example output:
6

Example input:
7
aacdeee

Example output:
6

Editorial:
Firstly, let's calculate the length of the prefix of equal letters (let it be $$$l$$$) and the length of the suffix of equal letters (let it be $$$r$$$). It can be done with two cycles with breaks. It is obvious that this prefix and suffix wouldn't overlap.
Then let's consider two cases: the first one is when $$$s_1 \ne s_n$$$ and the second one is when $$$s_1 = s_n$$$.
In the first case we can only remain either prefix or suffix of $$$s$$$ consisting only of equal letters. Then the answer is $$$l + r + 1$$$ (because we can remain from $$$1$$$ to $$$l$$$ letters on the prefix, from $$$1$$$ to $$$r$$$ on the suffix or empty string).
In the second case we can remain from $$$0$$$ to $$$l$$$ letters on the prefix and from $$$0$$$ to $$$r$$$ letters on the suffix. But now because $$$s_1 = s_n$$$ we can combine these ways, so the answer is $$$(l + 1) \cdot (r + 1)$$$.
And the bonus (this case is not belong to the given problem): if all letters in the string are equal then then answer is $$$\frac{n (n-1)}{2} + n$$$ because we can choose any substring of $$$s$$$ of length at least $$$2$$$ and any substring of length $$$1$$$.