#P17948. PalindromemordnilaP
PalindromemordnilaP
给定字符串 和字符 。
每次操作,从此前没有被选过的位置中等概率随机选择一个位置 ,将 改为 。即使该位置原来已经是 ,仍算作一次操作,该位置之后也不能再被选择。
重复操作,直到当前字符串首次成为回文串,然后立即停止。求所需操作次数的期望,对 取模。
如果初始字符串已经是回文串,答案为 。
回文串指从左往右和从右往左读取完全相同的字符串。
输入格式
第一行一个仅含小写英文字母的字符串 ()。
第二行一个小写英文字母 。
输出格式
输出一个整数,表示期望值对 取模的结果。对于有理数期望 ,输出 。
样例 1
输入
abcab
a
输出
4
样例 2
输入
abcdcbd
a
输出
177465668
样例 3
输入
aba
z
输出
0