Livet är alltid fullt av osäkerheter. Till exempel skulle man utifrån problemtiteln kunna tro att detta är ett strängproblem, men i själva verket är det inte det.

Du får en sträng $s$ och ett tecken $c$. Varje gång väljer du slumpmässigt en position $i$ som inte har valts tidigare, och ändrar $s_i$ till $c$ (om $s_i = c$ räknas det ändå som en operation). Du upprepar denna operation tills $s$ blir en palindrom, och stannar sedan. Du vill veta det förväntade antalet operationer som behövs.

Speciellt gäller att om $s$ redan är en palindrom från början, är svaret $0$.

Indata

Den första raden innehåller en sträng $s$ ($1 \le |s| \le 250000$), som garanterat endast består av små engelska bokstäver.

Den andra raden innehåller en liten engelsk bokstav $c$.

Utdata

Skriv ut ett heltal på en enda rad, som representerar väntevärdet modulo $998244353$.

Exempel

Indata 1

abcab
a

Utdata 1

4

Indata 2

abcdcbd
a

Utdata 2

177465668

Indata 3

aba
z

Utdata 3

0