Lífið er alltaf fullt af óvissu. Til dæmis gætirðu haldið út frá titli verkefnisins að þetta sé strengjaverkefni, en í raun og veru er það ekki svo.

Þér er gefinn strengur $s$ og stafur $c$. Í hvert skipti velurðu af handahófi staðsetningu $i$ sem hefur ekki verið valin áður, og breytir $s_i$ í $c$ (ef $s_i = c$ telst það samt sem ein aðgerð). Þú endurtekur þessa aðgerð þar til $s$ verður samhverfa (palindrome) og hættir þá. Þú vilt vita væntigildi fjölda aðgerða sem þarf.

Sér í lagi, ef $s$ er nú þegar samhverfa í upphafi, þá er svarið $0$.

Inntak

Fyrsta línan inniheldur streng $s$ ($1 \le |s| \le 250000$), sem tryggt er að samanstandi eingöngu af enskum lágstöfum.

Önnur línan inniheldur enskan lágstaf $c$.

Úttak

Prentaðu eina heiltölu á stakri línu, sem táknar væntigildið modulo $998244353$.

Dæmi

Inntak 1

abcab
a

Úttak 1

4

Inntak 2

abcdcbd
a

Úttak 2

177465668

Inntak 3

aba
z

Úttak 3

0