分数: 1000 点
问题陈述
有一系列单元向两个方向无限延伸。 你和 Snuke 玩以下游戏:
- 法官选择一个字符串 t 组成
B和S,称为回合字符串,并将其显示给两个玩家。 - 首先,Snuke 站在其中一个牢房上。
- 然后,对于每个 i = 1, ..., |t| 按照此顺序,会发生以下情况:
- 如果 i第一个字母 t is
B,轮到你了。您选择一个既不包含其他块也不包含 Snuke 的单元格,然后在该单元格上放置一个块。之后,如果与 Snuke 单元格相邻的两个单元格都被阻挡,则您获胜并且游戏结束。 - 如果 i第一个字母 t is
S,轮到Snuke了。他可能会移动到相邻的未封锁牢房,或者不做任何事情。
- 如果 i第一个字母 t is
- 如果游戏仍未结束,则 Snuke 获胜,游戏结束。
给你一个字符串 s 组成 B, S,和 ?。
如果 s 包含 Q ?s,有 2^Q 替换每个的方法 ? 与 B or S 并得到一个转字符串。
其中 2^Q 字符串,如果两位玩家都发挥最佳状态,您最终会获胜多少个?
求出模数的答案 998,244,353.
约束
- 1 \leq |s| \leq 10^6
- s 包括
B,S,和?.
输入
输入由标准输入按以下格式给出:
s
输出
打印答案。
示例输入 1
BSSBS
示例输出 1
0
你拿 1st 和 4第回合,Snuke 获得 2nd, 3rd,以及 5第回合。 在这种情况下,如果双方都发挥最佳,则 Snuke 获胜。
示例输入 2
?S?B????S????????B??????B??S??
示例输出 2
16777197