AT_agc050_c [AGC050C] Block Game

有一排无限延伸的格子。你和すぬけ君将用这些格子进行如下游戏。 - 裁判会制作一个只包含 `B` 和 `S` 的“回合字符串” $t$，并展示给两人。 - 首先，すぬけ君会站在某一个格子上。 - 然后，对于每个 $i=1,\ldots,|t|$，依次进行以下操作： - 如果 $t$ 的第 $i$ 个字符是 `B`，则轮到你操作。你可以选择一个没有其他方块或すぬけ君的格子，放置一个方块。放置后，如果すぬけ君的左右两侧格子都被方块占据，则你获胜，游戏结束。 - 如果 $t$ 的第 $i$ 个字符是 `S`，则轮到すぬけ君操作。すぬけ君可以移动到相邻的空格子，或者选择不动。 - 如果所有回合结束后游戏仍未结束，则すぬけ君获胜，游戏结束。 给定一个只包含 `B`、`S`、`?` 的字符串 $s$。其中 `?` 的数量为 $Q$。每个 `?` 可以独立替换为 `B` 或 `S`，因此一共有 $2^Q$ 种可能的“回合字符串”。在这 $2^Q$ 种情况下，若双方都采取最优策略，你能获胜的方案数是多少？请输出答案对 $998244353$ 取模的结果。

输入由标准输入给出，格式如下： > $s$

输出答案。

### 数据范围 - $1 \leq |s| \leq 10^6$ - $s$ 只包含 `B`、`S`、`?`。 ### 样例解释 1 第 $1$、$4$ 回合是你的回合，第 $2$、$3$、$5$ 回合是すぬけ君的回合。在这种情况下，双方都采取最优策略时，すぬけ君会获胜。 由 ChatGPT 4.1 翻译