P11749 「TPOI-1C」Standard Problem.

你是某知名 CP 网站的比赛审核员，经常收到一些 standard 的投稿。 你已经使用了太多次「quite standard」和「somewhat standard」作为回复了，因此这次你决定换一些。 首先你写下了你对这道题的评价 $s$，这里 $s$ 是一个仅包含英文小写字母的字符串。为了让投稿者知道自己的题目有多 standard，你又将这个字符串 $s$ 粘贴了 $k-1$ 次。最终，你的评价形成了一个字符串 $t = s^k$。 投稿者定义一个回复的 _怪异度_ 是这个字符串里的回文子串数量。请你求出你写下的回复 $t$ 的怪异度。由于这个值可能很大，你只需要输出它对 $998244353$ 取模的结果。 **形式化的**，给定字符串 $s$ 和整数 $k$，求 $s^k$（字符串 $s$ 拼接 $k$ 次）有多少回文子串（位置不同即算作不同），模 $998244353$。

无

无

### 样例解释 对于第一组数据，$t = s^2 = \texttt{abababab}$，共有 $20$ 个回文子串。 对于第三组数据，输入的字符串是 $(\texttt{abaab})^6$。 ### 数据范围 子任务 $1$ 为样例，不计分。 | 子任务 | 分数 | $n \le$ | $k \le$ | | :----------: | :----------: | :----------: | :----------: | | $2$ | $5$ | $2$ | $10^9$ | | $3$ | $30$ | $3 \cdot 10^6$ | $3 \cdot 10^6$ | | $4$ | $30$ | $2000$ | $10^9$ | | $5$ | $35$ | $3 \cdot 10^6$ | $10^9$ | - 子任务 $3$ 保证 $\sum k \le 3 \cdot 10^6$。 - 子任务 $4$ 保证 $\sum n^2 \le 2.5 \cdot 10^7$。