La vida siempre está llena de incertidumbres. Por ejemplo, podrías pensar por el título del problema que este es un problema de cadenas, pero en realidad no lo es.

Se te da una cadena $s$ y un carácter $c$. Cada vez, eliges al azar una posición $i$ que no haya sido elegida antes, y cambias $s_i$ por $c$ (si $s_i = c$, aun así cuenta como una operación). Repites esta operación hasta que $s$ se convierta en un palíndromo, y entonces te detienes. Quieres saber el número esperado de operaciones necesarias.

En particular, si $s$ ya es un palíndromo al principio, la respuesta es $0$.

Entrada

La primera línea contiene una cadena $s$ ($1 \le |s| \le 250000$), que se garantiza que consta únicamente de letras inglesas minúsculas.

La segunda línea contiene una letra inglesa minúscula $c$.

Salida

Imprime un entero en una sola línea, que represente el valor esperado módulo $998244353$.

Ejemplos

Entrada 1

abcab
a

Salida 1

4

Entrada 2

abcdcbd
a

Salida 2

177465668

Entrada 3

aba
z

Salida 3

0