题目描述

左右に無限に続くマスの列があります。 これを用いて、あなたとすぬけ君は以下のゲームをプレイします。

• 審判が、B と S からなる「ターン文字列」$t$ を作り、二人に見せる。
• まず、すぬけ君がマスのうち $1$ つの上に立つ。
• そして、各 $i\ =\ 1,\ ...,\ |t|$ について、この順番に以下が行われる。
  • $t$ の $i$ 文字目が B のとき、あなたのターンである。あなたは、他のブロックやすぬけ君を含まないマスを $1$ つ選び、ブロックを置く。設置後、すぬけ君の両隣のマスにともにブロックが置かれている場合、あなたの勝利でゲームが終了する。
  • $t$ の $i$ 文字目が S のとき、すぬけ君のターンである。すぬけ君は、隣の空きマスに移動するか、何もしない。
• この時点でゲームが終了していない場合、すぬけ君の勝利でゲームが終了する。

B, S, ? からなる文字列 $s$ が与えられます。 $s$ に含まれる ? の個数が $Q$ であるとき、? をそれぞれ B または S で置き換えてターン文字列とする方法は $2^Q$ 通り存在します。 これらの $2^Q$ 個のターン文字列のうち、両プレイヤーが最適に行動したときにあなたが勝利するようなものは何個あるでしょうか。 この答えを $998,244,353$ で割った余りを求めてください。

输入格式

入力は標準入力から以下の形式で与えられる。

$s$

输出格式

答えを出力せよ。

题目大意

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

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

给定字符串 $s$，其中仅含有 B、S 与 ? 三种字符。设 $s$ 中含有 $q$ 个 ?，有 $2^q$ 种填法将 $s$ 中的 ? 替换为 B 或 S，得到一个回合决定串。假设两名玩家都按最优策略操作，在这 $2^q$ 个串中，有多少种填法使得你能胜利呢？

请输出答案模 $998244353$ 的值。

$1\le |s|\le 10^6$。

BSSBS

0

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

16777197

提示

制約

• $1\ \leq\ |s|\ \leq\ 10^6$
• $s$ は B, S, ? からなる。

Sample Explanation 1

$1,\ 4$ ターン目があなたのターンで、$2,\ 3,\ 5$ ターン目がすぬけ君のターンです。 この場合、両者が最適に行動するとすぬけ君が勝つことがわかります。