Жизнь всегда полна неопределённости. Например, по названию задачи вы могли бы подумать, что это задача на строки, но на самом деле это не так.

Вам даны строка $s$ и символ $c$. Каждый раз вы случайно выбираете позицию $i$, которая не выбиралась ранее, и меняете $s_i$ на $c$ (если $s_i = c$, это всё равно считается одной операцией). Вы повторяете эту операцию до тех пор, пока $s$ не станет палиндромом, после чего останавливаетесь. Вы хотите узнать математическое ожидание количества необходимых операций.

В частности, если $s$ уже является палиндромом в самом начале, ответ равен $0$.

Входные данные

Первая строка содержит строку $s$ ($1 \le |s| \le 250000$), гарантированно состоящую только из строчных латинских букв.

Вторая строка содержит строчную латинскую букву $c$.

Выходные данные

Выведите в единственной строке одно целое число — математическое ожидание по модулю $998244353$.

Примеры

Входные данные 1

abcab
a

Выходные данные 1

4

Входные данные 2

abcdcbd
a

Выходные данные 2

177465668

Входные данные 3

aba
z

Выходные данные 3

0