Popping Balloons

시간 제한15초메모리 제한2048 MB

요약
매초 남은 풍선 하나가 무작위로 터질 때, 빨강, 노랑, 파랑 풍선이 처음으로 색깔 순서대로 정렬되는 기대 시간을 구한다.
난이도

어려움10점 중 9점

유형
확률, 조합론, 수학, 동적 계획법
정답자
아직 제출이 없습니다

문제

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.)

입력

The input has one line: a string ss (1≤∣s∣≤2⋅1051\le |s|\le 2\cdot 10^5) where each character is one of ‘B‘`B`, ‘Y‘`Y`, or ‘R‘`R` representing blue, yellow, and red respectively ---the colors of the initial balloons in the line.

출력

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,353998\\, 244\\, 353.

Formally, let p=998,244,353p = 998\\,244\\,353. It can be shown that the answer can be expressed as an irreducible fraction ab\frac{a}{b}, where aa and bb are non-negative integers and b≢0(modp)b \not \equiv 0 \pmod{p}. Print the integer xx with 0≤x<p0 \leq x < p and x≡a⋅b−1 mod px \equiv a \cdot b^{-1} \bmod p.

예제2

  1. 예제 1

    입력
    RYBB
    
    예상 출력
    831870297
    
  2. 예제 2

    입력
    YRBBR
    
    예상 출력
    598946615