Życie jest zawsze pełne niepewności. Na przykład z tytułu zadania można by pomyśleć, że jest to zadanie o napisach, ale w rzeczywistości tak nie jest.

Dany jest napis $s$ oraz znak $c$. Za każdym razem losowo wybierasz pozycję $i$, która nie była wcześniej wybrana, i zmieniasz $s_i$ na $c$ (jeśli $s_i = c$, nadal liczy się to jako jedna operacja). Powtarzasz tę operację, dopóki $s$ nie stanie się palindromem, a następnie kończysz. Chcesz poznać oczekiwaną liczbę potrzebnych operacji.

W szczególności, jeśli $s$ już na początku jest palindromem, odpowiedzią jest $0$.

Wejście

Pierwszy wiersz zawiera napis $s$ ($1 \le |s| \le 250000$), składający się wyłącznie z małych liter alfabetu angielskiego.

Drugi wiersz zawiera małą literę alfabetu angielskiego $c$.

Wyjście

Wypisz w pojedynczym wierszu jedną liczbę całkowitą, oznaczającą wartość oczekiwaną modulo $998244353$.

Przykłady

Wejście 1

abcab
a

Wyjście 1

4

Wejście 2

abcdcbd
a

Wyjście 2

177465668

Wejście 3

aba
z

Wyjście 3

0