← 返回题目列表

AtCoder · agc050_c

C. 方块游戏

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

有一系列单元向两个方向无限延伸。 你和 Snuke 玩以下游戏:

  • 法官选择一个字符串 t 组成 B 和 S,称为回合字符串,并将其显示给两个玩家。
  • 首先,Snuke 站在其中一个牢房上。
  • 然后,对于每个 i = 1, ..., |t| 按照此顺序,会发生以下情况:
    • 如果 i第一个字母 t is B,轮到你了。您选择一个既不包含其他块也不包含 Snuke 的单元格,然后在该单元格上放置一个块。之后,如果与 Snuke 单元格相邻的两个单元格都被阻挡,则您获胜并且游戏结束。
    • 如果 i第一个字母 t is S,轮到Snuke了。他可能会移动到相邻的未封锁牢房,或者不做任何事情。
  • 如果游戏仍未结束,则 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