AT_pakencamp_2022_day1_c Let's Make a Palindrome

题目描述

给定一个只包含小写英文字母和 `?` 的字符串 $S$。 请你计算,用任意小写英文字母替换字符串 $S$ 中每一个 `?`,可以构成多少种不同的回文串。 由于答案可能非常大,请输出答案对 $998244353$ 取模的结果。 回文定义:如果字符串 $T$ 满足,对于所有整数 $1 \leq i \leq |T|$,$T$ 的第 $i$ 个字符与倒数第 $i$ 个字符相同,则称 $T$ 是回文串。

输入格式

输入仅一行,表示字符串 $S$。

输出格式

输出一个整数,表示可以构成的不同回文串方案数对 $998244353$ 取模的结果。

说明/提示

### 样例解释 1 可以构成如下共 $26$ 种回文串:`aaa`、`aba`、`aca` 等等。 ### 样例解释 2 无法构成回文串。 ### 样例解释 3 注意要输出答案对 $998244353$ 取模的结果。 ### 数据范围 - $1 \leq |S| \leq 200000$ - $S$ 仅由小写英文字母和 `?` 组成。 由 ChatGPT 5 翻译