Định nghĩa một Ketek là một câu đọc xuôi hay đọc ngược đều giống nhau, xét theo từng từ. Ví dụ, ‘fall leaves after leaves fall’ là một Ketek vì các từ theo thứ tự ngược lại giống hệt thứ tự ban đầu.

Cho một xâu bao gồm các chữ cái thường và ký tự ‘?’, hãy đếm số lượng Ketek phân biệt mà bạn có thể tạo ra bằng cách thay thế mỗi ký tự ‘?’ bằng các chữ cái thường (mỗi ‘?’ tương ứng với một chữ cái), và tùy chọn thêm các khoảng trắng giữa các chữ cái. Lưu ý rằng một Ketek không được chứa bất kỳ ký tự ‘?’ nào; tất cả chúng phải được thay thế hoàn toàn bằng các chữ cái thường.

Ví dụ, nếu chúng ta bắt đầu với xâu ‘ababa’, chúng ta có thể tạo ra 3 Ketek khác nhau: ‘ababa’, ‘a bab a’ và ‘a b a b a’.

Nếu chúng ta bắt đầu với xâu ‘?x?z’, chúng ta có thể tạo ra 703 Ketek khác nhau:

• Có $26^2 = 676$ cách thay thế các dấu ‘?’ để tạo thành một Ketek gồm một từ.
• Thêm khoảng trắng để tạo thành ‘? x? z’. Có 26 cách để tạo thành một Ketek (dấu ‘?’ đầu tiên phải là z; dấu còn lại có thể là bất kỳ chữ cái thường nào).
• Thêm khoảng trắng để tạo thành ‘?x ?z’. Không có cách nào để tạo thành một Ketek.
• Thêm khoảng trắng để tạo thành ‘? x ? z’. Có 1 cách để tạo thành một Ketek (dấu ‘?’ đầu tiên phải là z; dấu thứ hai phải là x).

Tổng cộng là $676 + 26 + 0 + 1 = 703$.

Hai Ketek được coi là khác nhau nếu chúng có số lượng từ khác nhau, hoặc tồn tại một chỉ số từ mà tại đó các từ không giống nhau.

Dữ liệu vào

Dòng duy nhất của dữ liệu vào chứa một xâu $s$ ($1 \le |s| \le 30\,000$), bao gồm các chữ cái thường (‘a’ – ‘z’) và ký tự ‘?’.

Dữ liệu ra

In ra số lượng Ketek phân biệt có thể được tạo thành bằng cách thay thế các dấu ‘?’ bằng các chữ cái thường và thêm các khoảng trắng. Vì số lượng này có thể rất lớn, hãy in ra kết quả theo modulo $998\,244\,353$.

Ví dụ

Dữ liệu vào 1

ababa

Dữ liệu ra 1

3

Dữ liệu vào 2

?x?z

Dữ liệu ra 2

703