長さ $N$ の文字列を考えます。この文字列を $K$ 回繰り返したものを文字列 $S$ とします。この文字列がどれほど「WAC」であるか（WAC-ness）に興味があるため、この文字列の WAC-ness を求めるのがあなたのタスクです。

文字列の WAC-ness とは、その文字列において「WAC」が部分列として出現する回数のことです。

文字列の部分列とは、元の文字列から 0 文字以上の文字を削除し、残った文字の順序を変えずに得られる文字列のことです。2 つの部分列は、残されたインデックスの少なくとも 1 つが異なれば、異なるものとみなされます。例えば、文字列「AABC」において、インデックス 1, 3, 4 によって形成される部分列は、インデックス 2, 3, 4 によって形成される部分列とは異なります。

答えは非常に大きくなる可能性があるため、答えを $998\,244\,353$ で割った余りを出力してください。

入力

1 行目には、2 つの整数 $N$ と $K$ ($1 \le N \le 200\,000$, $1 \le K \le 200\,000$) が含まれます。これらは元の文字列の長さと、文字列 $S$ を形成するために元の文字列が繰り返される回数です。 2 行目には、英大文字からなる長さ $N$ の元の文字列が含まれます。

出力

文字列 $S$ の WAC-ness を $998\,244\,353$ で割った余りを出力してください。

入出力例

入力 1

5 1
WABCA

出力 1

1

入力 2

5 2
WABCA

出力 2

5