החיים תמיד מלאים בחוסר ודאות. לדוגמה, אתם עשויים לחשוב מכותרת הבעיה שזוהי בעיית מחרוזות, אך למעשה היא לא.

נתונים לכם מחרוזת $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