La vita è sempre piena di incertezze. Ad esempio, potresti pensare dal titolo del problema che questo sia un problema sulle stringhe, ma in realtà non lo è.

Ti vengono dati una stringa $s$ e un carattere $c$. Ogni volta, scegli casualmente una posizione $i$ che non è stata scelta prima, e cambi $s_i$ in $c$ (se $s_i = c$, conta comunque come un'operazione). Ripeti questa operazione finché $s$ non diventa un palindromo, e poi ti fermi. Vuoi conoscere il numero atteso di operazioni necessarie.

In particolare, se $s$ è già un palindromo all'inizio, la risposta è $0$.

Input

La prima riga contiene una stringa $s$ ($1 \le |s| \le 250000$), che è garantito sia composta solo da lettere minuscole dell'alfabeto inglese.

La seconda riga contiene una lettera minuscola dell'alfabeto inglese $c$.

Output

Stampa un intero su una singola riga, che rappresenta il valore atteso modulo $998244353$.

Esempi

Input 1

abcab
a

Output 1

4

Input 2

abcdcbd
a

Output 2

177465668

Input 3

aba
z

Output 3

0