Elämä on aina täynnä epävarmuutta. Esimerkiksi tehtävän otsikosta voisi luulla, että tämä on merkkijonotehtävä, mutta itse asiassa se ei ole.

Sinulle annetaan merkkijono $s$ ja merkki $c$. Joka kerta valitset satunnaisesti kohdan $i$, jota ei ole valittu aiemmin, ja muutat merkin $s_i$ merkiksi $c$ (jos $s_i = c$, se lasketaan silti yhdeksi operaatioksi). Toistat tätä operaatiota, kunnes merkkijonosta $s$ tulee palindromi, ja lopetat sitten. Haluat tietää tarvittavien operaatioiden lukumäärän odotusarvon.

Erityisesti, jos $s$ on palindromi jo alussa, vastaus on $0$.

Syöte

Ensimmäinen rivi sisältää merkkijonon $s$ ($1 \le |s| \le 250000$), jonka taataan koostuvan vain pienistä englantilaisista kirjaimista.

Toinen rivi sisältää pienen englantilaisen kirjaimen $c$.

Tuloste

Tulosta omalle rivilleen yksi kokonaisluku, joka kuvaa odotusarvoa modulo $998244353$.

Esimerkit

Syöte 1

abcab
a

Tuloste 1

4

Syöte 2

abcdcbd
a

Tuloste 2

177465668

Syöte 3

aba
z

Tuloste 3

0