问题描述

有一个无限延伸到两个方向的细胞序列。你和 Snuke 玩如下游戏：

• 裁判选择一个由 B 和 S 组成的字符串 $t$，称为回合字符串，并将其展示给两位玩家。
• 首先，Snuke 站在其中一个细胞上。
• 然后，对于每个 $i = 1, ..., |t|$，按照顺序进行如下操作：
  • 如果第 $i$ 个字母是 B，则轮到你行动。你选择一个既不包含其他方块也不包含 Snuke 的细胞，并在该细胞上放置一个方块。之后，如果两个与 Snuke 当前所在细胞相邻的细胞都被方块占据，你赢得游戏并游戏结束。
  • 如果第 $i$ 个字母是 S，则轮到 Snuke 行动。他可以移动到相邻的未被方块占据的细胞上，也可以不进行任何操作。
• 如果游戏仍未结束，Snuke 获胜并游戏结束。

给定一个由 B、S 和 ? 组成的字符串 $s$。如果 $s$ 中包含 $Q$ 个 ?，则有 $2^Q$ 种替换每个 ? 为 B 或 S 的方式，并得到一个回合字符串。在这 $2^Q$ 个字符串中，如果玩家都采取最优策略，有多少种方式会导致你获胜？将答案对 $998,244,353$ 取模。

约束条件

• $1 \leq |s| \leq 10^6$
• $s$ 由 B、S 和 ? 组成。

输入

输入以以下格式从标准输入给出：

$s$

输出

打印答案。

示例输入1

BSSBS

示例输出1

0

你负责第 1 和第4次行动，而 Snuke 负责第 2、3 和第 5 次行动。在这种情况下，如果双方玩家都采取最优策略，结果是 Snuke 获胜。

示例输入2

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

示例输出2

16777197