1 人解决，9 人已尝试。
1 份提交通过，共有 25 份提交。
9.9 EMB 奖励。
单点时限: 3.0 sec
内存限制: 512 MB
有一长度为 $n$ 的仅由 $0$ 和 $1$ 构成的字符串 $S$，某些位置的字符已经给定，其他位置的字符等概率取 $0$ 或 $1$，求 $S$ 的后缀自动机的结点数量的期望。
答案对 $998244353$ 取模。
关于后缀自动机的定义：请点这里
简单来说，如果我们定义集合 $endpos(t)$ 表示一个字符串 $t$ 在 $S$ 中每一次作为连续子串出现的结束位置，$S$ 的后缀自动机结点数量等于不同的 $endpos$ 个数。这里空集合即初始状态也算作结点。
第一行：一个整数 $n$，表示字符串长度。
第二行：一个长度为 $n$ 的字符串，包含 $0,1,?$ 三种字符，分别表示 $S$ 对应位置必定为 $0$，必定为 $1$，或随机取。
输出一行一个整数：表示答案对 $998244353$ 取模的结果。
3 10?
499122181
5 ?????
124780551
样例$1$解释：当 $?$ 处填 $0$ 时，后缀自动机有五个结点，填 $1$ 时有四个结点，所以答案为 $\frac{9}{2}$。
对于所有数据，满足 $1 \le n \le 36$。
本题共 $20$ 组数据，对于第 $i$ 组数据有 $n=\min(36,18+i)$。