配点 : $700$ 点

問題文

a,b,c からなる文字列 $S$ が与えられます。次の操作を $0$ 回以上繰り返して作ることのできる文字列としてありうるものの個数を $998244353$ で割ったあまりを求めてください。

• $1\leq i\leq |S|-1$ かつ $S$ の $i$ 文字目と $i+1$ 文字目が異なるような整数 $i$ を選ぶ。$S$ の $i$ 文字目と $i+1$ 文字目を両方、(a,b,c のうち)そのどちらとも異なる文字で置き換える。

制約

• $2 \leq |S| \leq 2 \times 10^5$
• $S$ は a,b,c からなる

入力

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

$S$

出力

操作を繰り返して作ることのできる文字列としてありうるものの個数を $998244353$ で割ったあまりを出力せよ。

abc

3

abc,aaa,ccc を作ることができます。

abbac

65

babacabac

6310

ababacbcacbacacbcbbcbbacbaccacbacbacba

148010497