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

Professor JAG, a researcher of sequences, is developing a new expression language. You are given an integer $N$ and a string $O=O_1O_2\cdots O_{N-1}$ consisting of `+` and `|`. Throughout this problem, a sequence with elements $a_1,a_2,\ldots,a_k$ is denoted by $[a_1,a_2,\ldots,a_k]$. Consider the following expression: $$ [1]\ O_1\ [2]\ O_2\ \cdots\ O_{N-1}\ [N] $$ Here, $O_i$ is the $i$-th character of the input string $O$ and is used as the operator between $[i]$ and $[i+1]$. Since operator precedence is not defined, we consider all possible ways to fully parenthesize this expression without changing the order of its operands or operators. Each expression obtained in this way is called a *valid expression*. For each expression $Z$, let $S(Z)$ denote the set of sequences represented by $Z$. The set $S(Z)$ is defined recursively as follows. - If $Z$ has the form `[i]` for some $i$ ($1\le i\le N$), then $S(Z)$ consists only of the one-element sequence $[i]$. - If $Z$ has the form `(X + Y)`, where $X$ and $Y$ are its left and right subexpressions, then $S(Z)$ consists of every sequence obtained by concatenating a sequence in $S(X)$ with a sequence in $S(Y)$. For example, if $S(X)$ contains $[1,3]$ and $S(Y)$ contains $[2,4]$, then $S(Z)$ contains $[1,3,2,4]$. - If $Z$ has the form `(X | Y)`, where $X$ and $Y$ are its left and right subexpressions, then $S(Z)=S(X)\cup S(Y)$. Different valid expressions may represent the same sequence. Find the number of distinct sequences represented by at least one valid expression. Since the answer may be large, output it modulo $998\,244\,353$.

The input consists of a single test case in the following format. ```text N O ``` The first line contains an integer $N$ ($2\le N\le 10^6$). The second line contains a string $O$ consisting of `+` and `|` ($|O|=N-1$).

Output the number of distinct sequences that can be represented, modulo $998\,244\,353$.

For the first sample, the expression is `[1]+[2]|[3]+[4]`. The following five valid expressions can be obtained by adding parentheses: - `((([1]+[2])|[3])+[4])` - `(([1]+[2])|([3]+[4]))` - `(([1]+([2]|[3]))+[4])` - `([1]+(([2]|[3])+[4]))` - `([1]+([2]|([3]+[4])))` The following four distinct sequences are represented by at least one of these valid expressions: - $[1,2]$ - $[1,2,4]$ - $[1,3,4]$ - $[3,4]$ Therefore, the answer is $4$.