$N$ 個のマスが横一列に並んでいます。
左から $i$ 番目のマスをマス $i$ とします。
英小文字・英大文字からなる文字列 $S$ が与えられ、マス $i$ には文字 $S_i$ が書かれています。
高橋くんははじめマス $1$ にいます。
高橋くんはいまいるマスに書かれている文字と異なる文字が書かれたマスを $1$ つ選び、そのマスに移動することを $K$ 回繰り返します。
より厳密には、マス $i$ にいるとき、$S_i≠S_j \ (1 ≤ j ≤ N)$ を満たすマス $j$ に移動します。


$K$ 回の移動後、文字 $T$ が書かれたマスにいる移動方法が何通りあるかを $998244353$ で割った余りを求めてください。
ただし、$2$ つの移動方法が異なるとは、ある $1≤ i ≤ K$ が存在して、$i$ 回目の移動後にいるマスが異なることを指します。

• $2 ≤ N ≤ 5×10^5$
• $1 ≤ K ≤ 10^{18}$
• $|S| = N$
• $|T| = 1$
• $S$ と $T$ は英小文字・英大文字からなる文字列
• $S$ に登場する文字の種類は $2$ 以上
• 入力される数値は全て整数

部分点

この問題には部分点が設定されています。
以下の条件を満たすテストケースにすべて正解したとき、記載された点数が与えられます。

1. (250点) $1 ≤ K ≤ 2×10^{5}$
2. (400点) 追加の制約なし

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

答えを $998244353$ で割った余りを求めてください。