H: Revenge of UMG

問題

'U', 'M', 'G' の三種類の文字からなる文字列 T に対し、1, 2, ..., |T| 文字目をそれぞれ T_1, T_2, ..., T_{|T|} と表すことにしたとき、以下の条件を満たす (i, j, k) の組の個数を、文字列 T の “UMG 数”と呼ぶことにします:

• 1 \leq i < j < k \leq |T|
• j - i = k - j
• T_i = 'U', T_j = 'M', T_k = 'G'

さて、'U', 'M', 'G', '?' の四種類の文字からなる文字列 S が与えられます。S の '?' をそれぞれ 'U', 'M', 'G' のいずれかに置き換えてできる文字列は、'?' の個数を N として 3^{N} 通り考えられますが、それぞれの文字列の UMG 数について総和をとったものを 998244353 で割ったあまりを求めてください。

入力形式

S

制約

• 3 \leq |S| \leq 2 \times 10^{5}
• S は 'U', 'M', 'G', '?' の四種類の文字からなる文字列である。

出力形式

答えを表す整数を一行に出力してください。998244353 で割ったあまりを出力することに注意してください。

入力例 1

?MG?

出力例 1

3

最初の '?' が 'U' でない場合には UMG 数は 0 になります。最初の '?' を 'U' としたとき、

• UMGU の UMG 数は 1
• UMGM の UMG 数は 1
• UMGG の UMG 数は 1

となり、合計値は 3 になります。

入力例 2

UUMMGGGUMG

出力例 2

4

入力例 3

?????G????U???M??????G?????M????G???U??????M???G??

出力例 3

648330088

998244353 で割ったあまりを答えてください。

---