Життя завжди сповнене невизначеності. Наприклад, із назви задачі ви могли б подумати, що це задача на рядки, але насправді це не так.

Вам задано рядок $s$ та символ $c$. Щоразу ви випадковим чином вибираєте позицію $i$, яка ще не вибиралася раніше, і змінюєте $s_i$ на $c$ (якщо $s_i = c$, це все одно рахується як одна операція). Ви повторюєте цю операцію доти, доки $s$ не стане паліндромом, після чого зупиняєтеся. Ви хочете дізнатися математичне сподівання кількості необхідних операцій.

Зокрема, якщо $s$ вже є паліндромом на самому початку, відповідь дорівнює $0$.

Вхідні дані

Перший рядок містить рядок $s$ ($1 \le |s| \le 250000$), який гарантовано складається лише з малих англійських літер.

Другий рядок містить малу англійську літеру $c$.

Вихідні дані

Виведіть в одному рядку одне ціле число — математичне сподівання за модулем $998244353$.

Приклади

Вхідні дані 1

abcab
a

Вихідні дані 1

4

Вхідні дані 2

abcdcbd
a

Вихідні дані 2

177465668

Вхідні дані 3

aba
z

Вихідні дані 3

0