Livet er alltid fullt av usikkerhet. For eksempel skulle man kanskje tro ut fra oppgavetittelen at dette er en strengoppgave, men egentlig er det ikke det.

Du får oppgitt en streng $s$ og et tegn $c$. Hver gang velger du tilfeldig en posisjon $i$ som ikke har blitt valgt før, og endrer $s_i$ til $c$ (hvis $s_i = c$, teller det fortsatt som én operasjon). Du gjentar denne operasjonen helt til $s$ blir et palindrom, og stopper deretter. Du vil vite det forventede antallet operasjoner som trengs.

Spesielt gjelder det at hvis $s$ allerede er et palindrom i utgangspunktet, er svaret $0$.

Inndata

Den første linjen inneholder en streng $s$ ($1 \le |s| \le 250000$), som garantert kun består av små engelske bokstaver.

Den andre linjen inneholder en liten engelsk bokstav $c$.

Utdata

Skriv ut ett heltall på én enkelt linje, som representerer forventningsverdien modulo $998244353$.

Eksempler

Inndata 1

abcab
a

Utdata 1

4

Inndata 2

abcdcbd
a

Utdata 2

177465668

Inndata 3

aba
z

Utdata 3

0