Cuộc sống luôn đầy rẫy những điều bất định. Ví dụ, nhìn vào tiêu đề bài toán, bạn có thể nghĩ rằng đây là một bài toán về xâu, nhưng thực tế lại không phải vậy.

Bạn được cho một xâu $s$ và một ký tự $c$. Mỗi lần, bạn chọn ngẫu nhiên một vị trí $i$ chưa từng được chọn trước đó, và đổi $s_i$ thành $c$ (nếu $s_i = c$, nó vẫn được tính là một thao tác). Bạn lặp lại thao tác này cho đến khi $s$ trở thành một xâu đối xứng (palindrome), rồi dừng lại. Bạn muốn biết kỳ vọng số thao tác cần thực hiện.

Đặc biệt, nếu ngay từ đầu $s$ đã là một xâu đối xứng, thì câu trả lời là $0$.

Dữ liệu vào

Dòng đầu tiên chứa một xâu $s$ ($1 \le |s| \le 250000$), đảm bảo chỉ gồm các chữ cái tiếng Anh viết thường.

Dòng thứ hai chứa một chữ cái tiếng Anh viết thường $c$.

Kết quả

In ra một số nguyên trên một dòng duy nhất, biểu thị giá trị kỳ vọng chia lấy dư cho $998244353$.

Ví dụ

Dữ liệu vào 1

abcab
a

Kết quả 1

4

Dữ liệu vào 2

abcdcbd
a

Kết quả 2

177465668

Dữ liệu vào 3

aba
z

Kết quả 3

0