AT_pakencamp_2023_day3_a ABC

長さ $ 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 $ 文字目のどちらとも等しくないものを挿入する。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ K $ $ S $

最終的な $ S $ としてありえる文字列の数を $ 998244353 $ で割った余りを出力してください。

### Sample Explanation 1 例えば、以下の手順で $ \mathtt{AABCBB} $ を作ることができます。 1. $ i=2 $ とする。 $ S $ の $ 2 $ 文字目の直後に $ \mathtt{C} $ を挿入する。 2. $ i=2 $ とする。 $ S $ の $ 2 $ 文字目の直後に $ \mathtt{B} $ を挿入する。 ### Constraints - $ 2\leq N\leq 2\times 10^5 $ - $ 1\leq K\leq 2\times 10^5 $ - $ S $ は $ \mathtt{A},\mathtt{B},\mathtt{C} $ のみからなる長さ $ N $ の文字列