C - Block Game Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

左右に無限に続くマスの列があります。 これを用いて、あなたとすぬけ君は以下のゲームをプレイします。

  • 審判が、B と S からなる「ターン文字列」t を作り、二人に見せる。
  • まず、すぬけ君がマスのうち 1 つの上に立つ。
  • そして、各 i = 1, ..., |t| について、この順番に以下が行われる。
    • t の i 文字目が B のとき、あなたのターンである。あなたは、他のブロックやすぬけ君を含まないマスを 1 つ選び、ブロックを置く。設置後、すぬけ君の両隣のマスにともにブロックが置かれている場合、あなたの勝利でゲームが終了する。
    • t の i 文字目が S のとき、すぬけ君のターンである。すぬけ君は、隣の空きマスに移動するか、何もしない。
  • この時点でゲームが終了していない場合、すぬけ君の勝利でゲームが終了する。

B, S, ? からなる文字列 s が与えられます。 s に含まれる ? の個数が Q であるとき、? をそれぞれ B または S で置き換えてターン文字列とする方法は 2^Q 通り存在します。 これらの 2^Q 個のターン文字列のうち、両プレイヤーが最適に行動したときにあなたが勝利するようなものは何個あるでしょうか。 この答えを 998,244,353 で割った余りを求めてください。

制約

  • 1 \leq |s| \leq 10^6
  • s は B, S, ? からなる。

入力

入力は標準入力から以下の形式で与えられる。

s

出力

答えを出力せよ。

入力例 1

BSSBS

出力例 1

0

1, 4 ターン目があなたのターンで、2, 3, 5 ターン目がすぬけ君のターンです。 この場合、両者が最適に行動するとすぬけ君が勝つことがわかります。

入力例 2

?S?B????S????????B??????B??S??

出力例 2

16777197

Score : 1000 points

Problem Statement

There is a sequence of cells that extends infinitely to both directions. You and Snuke play the following game:

  • The judge chooses a string t consisting of B and S, called turn string, and show it to both players.
  • First, Snuke stands on one of the cells.
  • Then, for each i = 1, ..., |t| in this order, the following happens:
    • If the i-th letter of t is B, it is your turn. You choose a cell that contains neither other blocks nor Snuke, and put a block on the cell. After that, if both of the two cells adjacent to Snuke's cell are blocked, you win and the game ends.
    • If the i-th letter of t is S, it is Snuke's turn. He may move to an adjacent unblocked cell, or doesn't do anything.
  • If the game still hasn't ended, Snuke wins and the game ends.

You are given a string s consisting of B, S, and ?. If s contains Q ?s, there are 2^Q ways to replace each ? with B or S and get a turn string. Among those 2^Q strings, how many will end up with your winning, in case both players play optimally? Find the answer modulo 998,244,353.

Constraints

  • 1 \leq |s| \leq 10^6
  • s consists of B, S, and ?.

Input

Input is given from Standard Input in the following format:

s

Output

Print the answer.

Sample Input 1

BSSBS

Sample Output 1

0

You take the 1st and the 4th turn, and Snuke takes the 2nd, the 3rd, and the 5th turn. In this case, if both players play optimally, it turns out that Snuke wins.

Sample Input 2

?S?B????S????????B??????B??S??

Sample Output 2

16777197