P12602 指鹿为马

原题来自 [2025 年洛谷愚人节比赛](https://www.luogu.com.cn/contest/231658)的 [F 题](T568349)。 --- 

给定一个字符串 $S$。 你有一个随机打字机。这个随机打字机打出的第一个字符一定是 $S$ 的第一位，之后打出的所有字符的概率分布只和它打出的上一个字符有关，并且按照如下规则进行： - 将字符串 $S$ 首尾相接连成一个环，记录下每种字符的下一个字符的种类和出现次数； - 那么，如果它打出的上一个字符是 $i$，此时它接下来打出字符 $j$ 的概率为 $\frac{cnt_{i,j}}{cnt_i}$。 - 其中，$cnt_i$ 为字符 $i$ 在 $S$ 中的出现次数，$cnt_{i,j}$ 为子串 $ij$ 在环状的 $S$ 中的出现次数。 每个新打出的字符会接在上一个打出的字符的后面。 当 $S$ （注意不是环状的 $S$）首次成为打字机打出的字符串的子串时，记录下当前打字机打出的字符总数。求这个总数的期望值模 $998244353$ 的结果。

一行一个字符串 $S$，由大小写字母和数字组成。长度不超过 $300000$。

一行一个整数表示答案模 $998244353$ 的结果。

设 $n$ 为字符串的长度。 | 测试点编号 | 特殊性质 A | 特殊性质 B | 无特殊性质 | | :-------------------: | :--------: | :--------: | :--------: | | $n\le 5$ | 1 | 2, 3 | 4, 5 | | $n\le 10$ | 6 | 7, 8 | 9, 10 | | $n\le 20$ | 11 | 12, 13 | 14, 15 | | $n\le 100$ | 16 | 17, 18 | 19, 20 | | $n\le 200$ | 21 | 22, 23 | 24, 25 | | $n\le 300$ | 26 | 27, 28 | 29, 30 | | $n\le 1000$ | 31 | 32, 33 | 34, 35 | | $n\le 2000$ | 36 | 37, 38 | 39, 40 | | $n\le 2\times 10^5$ | 41 | 42, 43 | 44, 45 | | $n\le 3\times 10^5$ | 46 | 47, 48 | 49, 50 | 特殊性质 A：保证输入的字符串是由一个没有重复字符的字符串重复若干次得到，比如 `cat`，`catcat`，`meowmeowmeow`。 特殊性质 B：保证输入的字符串的首字母在字符串中出现恰好一次。