P17531 [JAG 2026 Summer Camp #1] Professor JAG' s Language

研究序列的 JAG 教授正在开发一种新的表达式语言。给定一个整数 $N$，以及一个仅由 `+` 和 `|` 组成的字符串 $O=O_1O_2\cdots O_{N-1}$。在本题中，元素依次为 $a_1,a_2,\ldots,a_k$ 的序列记为 $[a_1,a_2,\ldots,a_k]$。 考虑以下表达式： $$ [1]\ O_1\ [2]\ O_2\ \cdots\ O_{N-1}\ [N] $$ 这里，$O_i$ 是输入字符串 $O$ 的第 $i$ 个字符，用作 $[i]$ 和 $[i+1]$ 之间的运算符。 由于没有规定运算符的优先级，我们考虑在不改变操作数和运算符顺序的前提下，为该表达式完整添加括号的所有方式。以这种方式得到的每个表达式称为一个**合法表达式**。 对于每个表达式 $Z$，设 $S(Z)$ 表示 $Z$ 所代表的序列的集合。集合 $S(Z)$ 递归定义如下： - 若 $Z$ 的形式为 `[i]`，其中 $1\le i\le N$，则 $S(Z)$ 中仅包含单元素序列 $[i]$。 - 若 $Z$ 的形式为 `(X + Y)`，其中 $X$、$Y$ 分别是它的左右子表达式，则 $S(Z)$ 包含将 $S(X)$ 中的一个序列与 $S(Y)$ 中的一个序列依次拼接所能得到的所有序列。例如，若 $S(X)$ 包含 $[1,3]$，而 $S(Y)$ 包含 $[2,4]$，则 $S(Z)$ 包含 $[1,3,2,4]$。 - 若 $Z$ 的形式为 `(X | Y)`，其中 $X$、$Y$ 分别是它的左右子表达式，则 $S(Z)=S(X)\cup S(Y)$。 不同的合法表达式可能代表同一个序列。求至少能被一个合法表达式表示的不同序列的数量。由于答案可能很大，输出其对 $998\,244\,353$ 取模的结果。

输入包含一组测试数据，格式如下： ```text N O ``` 第一行包含一个整数 $N$（$2\le N\le 10^6$）。第二行包含一个仅由 `+` 和 `|` 组成的字符串 $O$（$|O|=N-1$）。

输出能够被表示的不同序列的数量，对 $998\,244\,353$ 取模。

在第一个样例中，表达式为 `[1]+[2]|[3]+[4]`。 通过添加括号，可以得到以下五个合法表达式： - `((([1]+[2])|[3])+[4])` - `(([1]+[2])|([3]+[4]))` - `(([1]+([2]|[3]))+[4])` - `([1]+(([2]|[3])+[4]))` - `([1]+([2]|([3]+[4])))` 以下四个不同的序列至少能被这些合法表达式中的一个表示： - $[1,2]$ - $[1,2,4]$ - $[1,3,4]$ - $[3,4]$ 因此，答案为 $4$。