#P17948. PalindromemordnilaP

PalindromemordnilaP

给定字符串 ss 和字符 cc。

每次操作,从此前没有被选过的位置中等概率随机选择一个位置 ii,将 sis_i 改为 cc。即使该位置原来已经是 cc,仍算作一次操作,该位置之后也不能再被选择。

重复操作,直到当前字符串首次成为回文串,然后立即停止。求所需操作次数的期望,对 998244353998244353 取模。

如果初始字符串已经是回文串,答案为 00。

回文串指从左往右和从右往左读取完全相同的字符串。

输入格式

第一行一个仅含小写英文字母的字符串 ss(1≤∣s∣≤2500001\le|s|\le250000)。

第二行一个小写英文字母 cc。

输出格式

输出一个整数,表示期望值对 998244353998244353 取模的结果。对于有理数期望 p/qp/q,输出 p⋅q−1 mod 998244353p\cdot q^{-1}\bmod998244353。

样例 1

输入

abcab
a

输出

4

样例 2

输入

abcdcbd
a

输出

177465668

样例 3

输入

aba
z

输出

0