케텍 세기

단어 단위로 앞뒤를 읽어도 같은 문장을 케텍이라고 한다. 예를 들어 'fall leaves after leaves fall'은 단어 순서를 거꾸로 읽어도 원래 순서와 같으므로 케텍이다.

소문자와 '?' 문자로 이루어진 문자열이 주어진다. 모든 '?'를 소문자로 바꾸고, 필요하면 글자 사이에 공백을 넣어 만들 수 있는 서로 다른 케텍의 개수를 센다. 케텍에는 '?'가 남아 있을 수 없으므로, 모든 '?'를 반드시 소문자로 바꿔야 한다.

예를 들어 문자열이 'ababa'이면 케텍은 'ababa', 'a bab a', 'a b a b a' 세 가지를 만들 수 있다.

문자열이 '?x?z'이면 703개의 서로 다른 케텍을 만들 수 있다:

• '?'를 채워 공백 없이 단어 하나로 된 케텍을 만드는 방법은 $26^2 = 676$가지이다.
• 공백을 넣어 '? x? z'를 만든다. 케텍을 만드는 방법은 26가지이다 (첫 번째 '?'는 반드시 z이고, 두 번째는 아무 소문자나 될 수 있다).
• 공백을 한 개 넣어 '?x ?z'를 만든다. 케텍을 만들 방법이 없다.
• 공백을 넣어 '? x ? z'를 만든다. 케텍을 만드는 방법은 1가지이다 (첫 번째 '?'는 반드시 z이고, 두 번째는 반드시 x이다).

합계는 $676 + 26 + 0 + 1 = 703$이다.

두 케텍은 단어 개수가 다르거나, 어떤 단어 위치에서 단어가 다르면 서로 다른 것이다.

한 줄에 문자열 $s$가 주어진다 ($1 \le |s| \le 30\,000$). $s$는 소문자 'a'부터 'z'까지와 '?' 문자로 이루어져 있다.

'?'를 소문자로 바꾸고 공백을 넣어 만들 수 있는 서로 다른 케텍의 개수를 출력한다. 개수가 클 수 있으므로 $998\,244\,353$으로 나눈 나머지를 출력한다.