A GE-string is a string where each of its characters is either $$$\texttt{G}$$$ or $$$\texttt{E}$$$. A GE-string is said to be alternating if and only if there is no pair of the same character that are adjacent.
We can partition a GE-string into one or more subsequences of characters such that each character is in exactly one subsequence. A partition is valid if and only if each subsequence is alternating. A valid partition of a GE-string is minimum if and only if it partitions the GE-string into the minimum number of subsequences out of all possible valid partitions for that GE-string.
The score of a GE-string is the number of different minimum valid partitions for that GE-string. Two partitions are different if and only if two characters are in the same subsequence in one partition, but they are in different subsequences in the other partition.
Kantipa has a string $$$S$$$ that is a GE-string of length $$$N$$$. Calculate the score of $$$S$$$. Print the answer modulo $$$998\,244\,353$$$.
The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 200\,000$$$) — the length of $$$S$$$.
The second line contains a string $$$S$$$ of length $$$N$$$ consisting of characters $$$\texttt{G}$$$ or $$$\texttt{E}$$$.
An integer representing the score of $$$S$$$, modulo $$$998\,244\,353$$$.
7GEGGGEG
9
6EEEEEE
1
In the first example, the minimum number of subsequences out of all possible valid partitions is $$$3$$$. There are $$$9$$$ different ways to partition $$$\texttt{GEGGGEG}$$$ into $$$3$$$ subsequences. The following are possible sets of the sets of indices for the $$$3$$$ subsequences:
In the second example, there's only one possible minimum valid partition, which is achieved by making every single character its own subsequence.
