人生は常に不確実性に満ちています。例えば、問題タイトルからこれは文字列の問題だと思うかもしれませんが、実際にはそうではありません。

文字列 $s$ と文字 $c$ が与えられます。毎回、まだ選ばれていない位置 $i$ をランダムに 1 つ選び、$s_i$ を $c$ に変更します（もともと $s_i = c$ であったとしても 1 回の操作として数えます）。$s$ が回文になるまでこの操作を繰り返し、回文になった時点で終了します。必要な操作回数の期待値を求めてください。

特に、最初から $s$ がすでに回文である場合、答えは $0$ です。

入力

1 行目には文字列 $s$（$1 \le |s| \le 250000$）が与えられます。$s$ は英小文字のみからなることが保証されます。

2 行目には英小文字 $c$ が与えられます。

出力

期待値を $998244353$ で割った余りを表す整数を 1 行に出力してください。

入出力例

入力 1

abcab
a

出力 1

4

入力 2

abcdcbd
a

出力 2

177465668

入力 3

aba
z

出力 3

0