AT_utpc2024_o One Different Inequality

给定一个整数 $N$，以及一个长度为 $N-1$ 的只包含 `` 的字符串 $S$。 我们考虑 $1, 2, \dots, N$ 的一个排列 $P = (P_1, P_2, \dots, P_N)$。 当 $P$ 满足下列条件时，称 $P$ 是一个**良好排列**： - 对于所有 $i\ (1 \leq i \leq N-1)$，若 $S$ 的第 $i$ 个字符为 ``，则 $P_i > P_{i+1}$。 又，当 $P$ 满足下列所有条件时，称 $P$ 是一个**优秀排列**： - $P$ 是一个良好排列。 - 在满足 $|P_i - P_{i+1}| = 1$ 的 $i\ (1 \leq i \leq N-1)$ 的个数在所有良好排列中最大。 请计算优秀排列的个数，输出对 $998244353$ 取模的结果。

输入以如下格式从标准输入给出： > $N\quad S$

请输出一个整数，表示答案。

## 部分分 - 若能解决满足 $2 \leq N \leq 10000$ 的额外限制，则可以获得 $20$ 分。 ## 样例解释 1 良好排列的例子有 $(1,2,5,4,3)$ 和 $(2,3,5,4,1)$，对应满足 $|P_i-P_{i+1}|=1$ 的 $i$ 数分别为 $3$ 和 $2$。 能证明在所有良好排列中，$|P_i-P_{i+1}|=1$ 的最大个数是 $3$，而优秀排列有 $(1,2,5,4,3)$ 和 $(3,4,5,2,1)$ 两种。 # 数据范围 - $N$ 是整数 - $2 \leq N \leq 2 \times 10^5$ - $S$ 是长度为 $N-1$、仅由 `` 组成的字符串。 由 ChatGPT 5 翻译