考慮一個長度為 $N$ 的字串。令字串 $S$ 為該字串重複 $K$ 次後的結果。你對這個字串的「WAC 度」（WAC-ness）感興趣，因此你的任務是找出該字串的 WAC 度。

一個字串的 WAC 度是指「WAC」作為該字串的子序列出現的次數。

子序列是指從給定序列中刪除零個或多個字元，且不改變剩餘字元順序後所得到的字串。若兩個子序列所使用的原始索引中至少有一個不同，則視為不同的子序列。例如，在字串「AABC」中，由索引 1、3 和 4 組成的子序列與由索引 2、3 和 4 組成的子序列是不同的。

由於答案可能非常大，請將答案對 $998\,244\,353$ 取模後輸出。

輸入格式

第一行包含兩個整數 $N$ 和 $K$ ($1 \le N \le 200\,000$, $1 \le K \le 200\,000$)，分別為原始字串的長度以及該字串重複形成 $S$ 的次數。第二行（最後一行）包含該長度為 $N$ 的原始字串，由大寫英文字母組成。

輸出格式

輸出字串 $S$ 的 WAC 度，並對 $998\,244\,353$ 取模。

範例

範例輸入 1

5 1
WABCA

範例輸出 1

1

範例輸入 2

5 2
WABCA

範例輸出 2

5