Das Leben ist immer voller Ungewissheiten. Zum Beispiel könnte man aufgrund des Problemtitels denken, dass dies ein Zeichenkettenproblem ist, aber tatsächlich ist es keines.

Gegeben sind eine Zeichenkette $s$ und ein Zeichen $c$. Jedes Mal wählen Sie zufällig eine Position $i$ aus, die zuvor noch nicht gewählt wurde, und ändern $s_i$ in $c$ (falls $s_i = c$ gilt, zählt dies trotzdem als eine Operation). Sie wiederholen diese Operation, bis $s$ zu einem Palindrom wird, und hören dann auf. Sie möchten den Erwartungswert der benötigten Anzahl von Operationen wissen.

Insbesondere ist die Antwort $0$, falls $s$ bereits zu Beginn ein Palindrom ist.

Eingabe

Die erste Zeile enthält eine Zeichenkette $s$ ($1 \le |s| \le 250000$), die garantiert nur aus englischen Kleinbuchstaben besteht.

Die zweite Zeile enthält einen englischen Kleinbuchstaben $c$.

Ausgabe

Geben Sie eine einzelne ganze Zahl in einer Zeile aus, die den Erwartungswert modulo $998244353$ darstellt.

Beispiele

Eingabe 1

abcab
a

Ausgabe 1

4

Eingabe 2

abcdcbd
a

Ausgabe 2

177465668

Eingabe 3

aba
z

Ausgabe 3

0