El profesor JAG, un investigador de sucesiones, está desarrollando un nuevo lenguaje de expresiones. Se te da un entero $N$ y una cadena $O = O_1 O_2 \cdots O_{N-1}$ formada por + y |. A lo largo de este problema, una sucesión con elementos $a_1, a_2, \ldots, a_k$ se denota por $[a_1, a_2, \ldots, a_k]$.

Considera la siguiente expresión:

$$[1]\ O_1\ [2]\ O_2\ \ldots\ O_{N-1}\ [N]$$

Aquí, $O_i$ es el $i$-ésimo carácter de la cadena de entrada $O$ y se utiliza como el operador entre $[i]$ y $[i + 1]$.

Como la precedencia de operadores no está definida, consideramos todas las formas posibles de colocar paréntesis completamente en esta expresión sin cambiar el orden de sus operandos ni de sus operadores. Cada expresión obtenida de esta manera se denomina una expresión válida.

Para cada expresión $Z$, sea $S(Z)$ el conjunto de sucesiones representadas por $Z$. El conjunto $S(Z)$ se define recursivamente de la siguiente manera:

• Si $Z$ tiene la forma [i] para algún $i$ ($1 \le i \le N$), entonces $S(Z)$ consta únicamente de la sucesión de un solo elemento $[i]$.
• Si $Z$ tiene la forma (X + Y), donde $X$ e $Y$ son sus subexpresiones izquierda y derecha, entonces $S(Z)$ consta de todas las sucesiones obtenidas al concatenar una sucesión en $S(X)$ con una sucesión en $S(Y)$. Por ejemplo, si $S(X)$ contiene $[1, 3]$ y $S(Y)$ contiene $[2, 4]$, entonces $S(Z)$ contiene $[1, 3, 2, 4]$.
• Si $Z$ tiene la forma (X | Y), donde $X$ e $Y$ son sus subexpresiones izquierda y derecha, entonces $S(Z) = S(X) \cup S(Y)$.

Diferentes expresiones válidas pueden representar la misma sucesión. Halla el número de sucesiones distintas representadas por al menos una expresión válida. Como la respuesta puede ser muy grande, imprímela módulo $998\,244\,353$.

Entrada

La entrada consta de un único caso de prueba con el siguiente formato:

$$\begin{aligned} &N \\ &O \end{aligned}$$

La primera línea contiene un entero $N$ ($2 \le N \le 10^6$). La segunda línea contiene una cadena $O$ formada por + y | ($|O| = N - 1$).

Salida

Imprime el número de sucesiones distintas que pueden ser representadas, módulo $998\,244\,353$.

Ejemplos

Entrada 1

4
+|+

Salida 1

4

Entrada 2

7
||+|||

Salida 2

17

Entrada 3

17
+|||+|+++||||+|+

Salida 3

1774

Nota

Para el primer ejemplo, la expresión es [1]+[2]|[3]+[4].

Las siguientes cinco expresiones válidas se pueden obtener añadiendo paréntesis:

• ((([1]+[2])|[3])+[4])
• (([1]+[2])|([3]+[4]))
• (([1]+([2]|[3]))+[4])
• ([1]+(([2]|[3])+[4]))
• ([1]+([2]|([3]+[4])))

Las siguientes cuatro sucesiones distintas están representadas por al menos una de estas expresiones válidas:

• $[1, 2]$
• $[1, 2, 4]$
• $[1, 3, 4]$
• $[3, 4]$

Por lo tanto, la respuesta es $4$.