Ketek이란 단어 단위로 앞에서부터 읽으나 뒤에서부터 읽으나 동일한 문장을 의미한다. 예를 들어, 'fall leaves after leaves fall'은 단어의 역순이 원래 순서와 같으므로 Ketek이다.

소문자와 문자 '?'로 구성된 문자열이 주어질 때, 모든 '?'를 소문자로 바꾸고(각 '?'마다 한 글자씩), 선택적으로 글자 사이에 공백을 추가하여 만들 수 있는 서로 다른 Ketek의 개수를 구하시오. Ketek에는 '?'가 포함될 수 없으며, 모든 '?'는 반드시 소문자로 대체되어야 함에 유의하라.

예를 들어, 문자열 'ababa'로 시작하면 3개의 서로 다른 Ketek을 만들 수 있다: 'ababa', 'a bab a', 'a b a b a'.

만약 문자열 '?x?z'로 시작한다면, 703개의 서로 다른 Ketek을 만들 수 있다:

• $26^2 = 676$가지 방법으로 '?'를 대체하여 한 단어짜리 Ketek을 만들 수 있다.
• 공백을 추가하여 '? x? z' 형태를 만든다. Ketek을 만드는 방법은 26가지이다 (첫 번째 '?'는 반드시 z여야 하며, 다른 하나는 임의의 소문자가 될 수 있다).
• 공백을 추가하여 '?x ?z' 형태를 만든다. Ketek을 만드는 방법은 없다.
• 공백을 추가하여 '? x ? z' 형태를 만든다. Ketek을 만드는 방법은 1가지이다 (첫 번째 '?'는 반드시 z여야 하며, 두 번째는 반드시 x여야 한다).

총합은 $676 + 26 + 0 + 1 = 703$이다.

두 Ketek은 단어의 개수가 다르거나, 특정 단어 인덱스에서 단어가 서로 다를 경우 다른 것으로 간주한다.

입력

입력은 소문자('a' – 'z')와 문자 '?'로 구성된 문자열 $s$ ($1 \le |s| \le 30\,000$) 한 줄로 주어진다.

출력

'?'를 소문자로 대체하고 공백을 추가하여 만들 수 있는 서로 다른 Ketek의 개수를 출력한다. 이 수는 매우 클 수 있으므로 $998\,244\,353$으로 나눈 나머지를 출력한다.

예제

입력 1

ababa

출력 1

3

입력 2

?x?z

출력 2

703