問題文

長さ N の文字列 S があります。S の各文字は \mathtt{A},\mathtt{B},\mathtt{C} のいずれかです。

これから S に以下の操作を K 回行います。最終的な S としてありえる文字列の数を 998244353 で割った余りを求めてください。

• 1\leq i\leq |S|-1 を満たす整数 i を選ぶ。S の i 文字目と i+1 文字目が等しいならば、S の i 文字目の直後に S の i 文字目と等しい文字を挿入する。そうでないならば、S の i 文字目の直後に \mathtt{A},\mathtt{B},\mathtt{C} のうち S の i 文字目と i+1 文字目のどちらとも等しくないものを挿入する。

制約

• 2\leq N\leq 2\times 10^5
• 1\leq K\leq 2\times 10^5
• S は \mathtt{A},\mathtt{B},\mathtt{C} のみからなる長さ N の文字列

入力例 1

4 2
AABB

出力例 1

7

例えば、以下の手順で \mathtt{AABCBB} を作ることができます。

1. i=2 とする。S の 2 文字目の直後に \mathtt{C} を挿入する。
2. i=2 とする。S の 2 文字目の直後に \mathtt{B} を挿入する。

入力例 2

2 10
CC

出力例 2

1

入力例 3

19 21
AABCBAACCCACACCCBAB

出力例 3

957795267