Problem J
Popping Balloons
The ICPC logo has three colors: blue, yellow, and red. The NAC volunteers have just inflated a huge number of balloons in these colors and arranged them in a line. They next need to sort the balloons by color before they can give them out to contestants.
Unfortunately, due to the Orlando heat, the balloons begin to randomly pop: each second, a random remaining balloon pops (and the volunteers remove the debris from the line). This isn’t all bad: maybe if the NAC volunteers wait long enough, the balloons will become sorted by chance? Compute the expected number of seconds until the first time that all blue balloons come before all yellow and red balloons, and all yellow balloons come before all red balloons. (These conditions are satisfied even if they are vacuously true: for example, if there are no blue balloons at all remaining, then it is true that all blue balloons come before all yellow and red balloons.)
Input
The input has one line: a string $s$ ($1\le |s|\le 2\cdot 10^5$) where each character is one of $\texttt{B}$, $\texttt{Y}$, or $\texttt{R}$ representing blue, yellow, and red respectively —the colors of the initial balloons in the line.
Output
Print the expected number of seconds that elapse before the first time that all blue balloons come before all yellow and red balloons, and all yellow balloons come before all red balloons. Since this number might not be an integer, print it modulo $998\, 244\, 353$.
Formally, let $p = 998\, 244\,
353$. It can be shown that the answer can be expressed
as an irreducible fraction $\frac{a}{b}$, where $a$ and $b$ are non-negative integers and
$b \not\equiv 0 \pmod{p}$.
Print the integer $x$ with
$0 \leq x < p$ and
$x \equiv a \cdot b^{-1} \bmod
p$.
Sample Explanation
In Sample Input 1, the expected time until the balloon colors first become sorted in the correct order is $\frac{17}{6} = 2\cdot \frac{1}{6} + 3 \cdot \frac{5}{6}$ seconds: the only way for the balloon colors to be sorted correctly after $2$ seconds is if the first two balloons to pop are the yellow and red balloon (in either order). The probability that these balloons pop before either blue balloon is $\frac{1}{6}$. Otherwise (with probability $\frac{5}{6}$) the balloon colors will automatically be sorted after $3$ seconds, when there is only one balloon left. Since $6^{-1} \equiv 166\, 374\, 059\pmod{p}$, the answer is $17\cdot 166\, 374\, 059\equiv 831\, 870\, 297\pmod{p}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
RYBB |
831870297 |
| Sample Input 2 | Sample Output 2 |
|---|---|
YRBBR |
598946615 |
