الحياة مليئة دائمًا بعدم اليقين. على سبيل المثال، قد تظن من عنوان المسألة أن هذه مسألة سلاسل نصية، لكنها في الواقع ليست كذلك.

تُعطى لك سلسلة نصية $s$ وحرف $c$. في كل مرة، تختار عشوائيًا موضعًا $i$ لم يتم اختياره من قبل، وتغيّر $s_i$ إلى $c$ (إذا كان $s_i = c$، فإنه لا يزال يُحتسب كعملية واحدة). تكرر هذه العملية حتى تصبح $s$ سلسلة متناظرة (palindrome)، ثم تتوقف. تريد معرفة القيمة المتوقعة لعدد العمليات اللازمة.

على وجه الخصوص، إذا كانت $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