Hidup selalu penuh dengan ketidakpastian. Sebagai contoh, Anda mungkin mengira dari judulnya bahwa ini adalah masalah string, tetapi sebenarnya bukan.

Anda diberikan sebuah string $s$ dan sebuah karakter $c$. Setiap kali, Anda memilih secara acak sebuah posisi $i$ yang belum pernah dipilih sebelumnya, lalu mengubah $s_i$ menjadi $c$ (jika $s_i = c$, hal tersebut tetap dihitung sebagai satu operasi). Anda mengulangi operasi ini hingga $s$ menjadi sebuah palindrom, lalu berhenti. Anda ingin mengetahui nilai ekspektasi dari banyaknya operasi yang diperlukan.

Secara khusus, jika $s$ sudah merupakan palindrom sejak awal, maka jawabannya adalah $0$.

Masukan

Baris pertama berisi sebuah string $s$ ($1 \le |s| \le 250000$), yang dijamin hanya terdiri dari huruf kecil bahasa Inggris.

Baris kedua berisi sebuah huruf kecil bahasa Inggris $c$.

Keluaran

Keluarkan satu bilangan bulat dalam satu baris, yang menyatakan nilai ekspektasi modulo $998244353$.

Contoh

Masukan 1

abcab
a

Keluaran 1

4

Masukan 2

abcdcbd
a

Keluaran 2

177465668

Masukan 3

aba
z

Keluaran 3

0