인생은 언제나 불확실성으로 가득 차 있다. 예를 들어, 문제 제목만 보고 이 문제가 문자열 문제라고 생각할지도 모르지만, 실제로는 그렇지 않다.

문자열 $s$와 문자 $c$가 주어진다. 매번 이전에 선택된 적이 없는 위치 $i$를 무작위로 하나 선택하여 $s_i$를 $c$로 바꾼다($s_i = c$인 경우에도 한 번의 연산으로 센다). $s$가 회문(palindrome)이 될 때까지 이 연산을 반복한 뒤 멈춘다. 필요한 연산 횟수의 기댓값을 구하여라.

특히, 처음부터 $s$가 이미 회문이라면 답은 $0$이다.

입력

첫 번째 줄에 문자열 $s$ ($1 \le |s| \le 250000$)가 주어지며, 영어 소문자로만 이루어져 있음이 보장된다.

두 번째 줄에 영어 소문자 $c$가 주어진다.

출력

기댓값을 $998244353$으로 나눈 나머지를 나타내는 정수를 한 줄에 출력한다.

예제

입력 1

abcab
a

출력 1

4

입력 2

abcdcbd
a

출력 2

177465668

입력 3

aba
z

출력 3

0