#agc050c. [agc050_c]Block Game

[agc050_c]Block Game

有一个由房间组成的序列,其向左右两端无限延伸。你和 Snuke 在玩下面的游戏:

  • 裁判给出一个由 BS 组成的字符串 tt,名为回合决定串,并将它展示给两名玩家。
  • 首先,Snuke 站在其中一个房间里。
  • 随后,对于每个 i=1,2,,ti = 1,2,\dots,|t|,发生如下的事件:
    • 如果 tt 中第 ii 个字母为 B,则这是你的回合。你会选择一个其中没有障碍或 Snuke 的房间,在其中放置一个障碍。这之后,如果 Snuke 所在房间左右两侧的房间均放置有障碍,则你胜利,游戏结束。
    • 如果 tt 中第 ii 个字母为 S,则这是 Snuke 的回合。他可以移动到与当前所在房间相邻且无障碍的房间,或什么都不做。
  • 如果 t|t| 轮后游戏仍未结束,则 Snuke 胜利,游戏结束。

给定字符串 ss,其中仅含有 BS? 三种字符。设 ss 中含有 qq?,有 2q2^q 种填法将 ss 中的 ? 替换为 BS,得到一个回合决定串。假设两名玩家都按最优策略操作,在这 2q2^q 个串中,有多少种填法使得你能胜利呢?

请输出答案模 998244353998244353 的值。

1s1061\le |s|\le 10^6