ชีวิตเต็มไปด้วยความไม่แน่นอนเสมอ ตัวอย่างเช่น คุณอาจคิดจากชื่อโจทย์ว่านี่คือโจทย์ปัญหาเกี่ยวกับสตริง แต่ความจริงแล้วไม่ใช่

คุณได้รับสตริง $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