Life is always full of uncertainties. For example, you might think from the problem title that this is a string problem, but actually it is not.

You are given a string $s$ and a character $c$. Each time, you randomly choose a position $i$ that has not been chosen before, and change $s_i$ to $c$ (if $s_i = c$, it still counts as one operation). You repeat this operation until $s$ becomes a palindrome, and then stop. You want to know the expected number of operations needed.

In particular, if $s$ is already a palindrome at the beginning, the answer is $0$.

Input

The first line contains a string $s$ ($1 \le |s| \le 250000$), guaranteed to consist only of lowercase English letters.

The second line contains a lowercase English letter $c$.

Output

Output one integer on a single line, representing the expected value modulo $998244353$.

Examples

Input 1

abcab
a

Output 1

4

Input 2

abcdcbd
a

Output 2

177465668

Input 3

aba
z

Output 3

0