#agc050c. [agc050_c]Block Game
[agc050_c]Block Game
有一个由房间组成的序列,其向左右两端无限延伸。你和 Snuke 在玩下面的游戏:
- 裁判给出一个由
B
和S
组成的字符串 ,名为回合决定串,并将它展示给两名玩家。 - 首先,Snuke 站在其中一个房间里。
- 随后,对于每个 ,发生如下的事件:
- 如果 中第 个字母为
B
,则这是你的回合。你会选择一个其中没有障碍或 Snuke 的房间,在其中放置一个障碍。这之后,如果 Snuke 所在房间左右两侧的房间均放置有障碍,则你胜利,游戏结束。 - 如果 中第 个字母为
S
,则这是 Snuke 的回合。他可以移动到与当前所在房间相邻且无障碍的房间,或什么都不做。
- 如果 中第 个字母为
- 如果 轮后游戏仍未结束,则 Snuke 胜利,游戏结束。
给定字符串 ,其中仅含有 B
、S
与 ?
三种字符。设 中含有 个 ?
,有 种填法将 中的 ?
替换为 B
或 S
,得到一个回合决定串。假设两名玩家都按最优策略操作,在这 个串中,有多少种填法使得你能胜利呢?
请输出答案模 的值。
。