La vie est toujours pleine d'incertitudes. Par exemple, vous pourriez penser d'après le titre du problème qu'il s'agit d'un problème de chaînes de caractères, mais en réalité ce n'en est pas un.

On vous donne une chaîne de caractères $s$ et un caractère $c$. À chaque étape, vous choisissez aléatoirement une position $i$ qui n'a pas encore été choisie, et vous remplacez $s_i$ par $c$ (si $s_i = c$, cela compte quand même pour une opération). Vous répétez cette opération jusqu'à ce que $s$ devienne un palindrome, puis vous vous arrêtez. Vous voulez connaître le nombre espéré d'opérations nécessaires.

En particulier, si $s$ est déjà un palindrome au départ, la réponse est $0$.

Entrée

La première ligne contient une chaîne de caractères $s$ ($1 \le |s| \le 250000$), garantie comme étant composée uniquement de lettres minuscules de l'alphabet anglais.

La deuxième ligne contient une lettre minuscule de l'alphabet anglais $c$.

Sortie

Affichez un entier sur une seule ligne, représentant l'espérance modulo $998244353$.

Exemples

Entrée 1

abcab
a

Sortie 1

4

Entrée 2

abcdcbd
a

Sortie 2

177465668

Entrée 3

aba
z

Sortie 3

0