题目描述

有一排无限延伸的格子。你和すぬけ君将用这些格子进行如下游戏。

• 裁判会制作一个只包含 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

输入

BSSBS

输出

0

样例 2

输入

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

输出

16777197

说明/提示

数据范围

• $1 \leq |s| \leq 10^6$
• $s$ 只包含 B、S、?。

样例解释 1

第 $1$、$4$ 回合是你的回合，第 $2$、$3$、$5$ 回合是すぬけ君的回合。在这种情况下，双方都采取最优策略时，すぬけ君会获胜。

由 ChatGPT 4.1 翻译