Le professeur JAG, chercheur spécialiste des suites, développe un nouveau langage d'expressions. On vous donne un entier $N$ et une chaîne de caractères $O = O_1 O_2 \cdots O_{N-1}$ composée de + et de |. Tout au long de ce problème, une suite d'éléments $a_1, a_2, \ldots, a_k$ est notée $[a_1, a_2, \ldots, a_k]$.

Considérons l'expression suivante :

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

Ici, $O_i$ est le $i$-ème caractère de la chaîne d'entrée $O$ et sert d'opérateur entre $[i]$ et $[i + 1]$.

Comme la priorité des opérateurs n'est pas définie, nous considérons toutes les façons possibles de parenthéser complètement cette expression sans changer l'ordre de ses opérandes ni de ses opérateurs. Chaque expression obtenue de cette manière est appelée une expression valide.

Pour chaque expression $Z$, soit $S(Z)$ l'ensemble des suites représentées par $Z$. L'ensemble $S(Z)$ est défini récursivement comme suit :

• Si $Z$ est de la forme [i] pour un certain $i$ ($1 \le i \le N$), alors $S(Z)$ est constitué uniquement de la suite à un seul élément $[i]$.
• Si $Z$ est de la forme (X + Y), où $X$ et $Y$ sont ses sous-expressions gauche et droite, alors $S(Z)$ est constitué de toutes les suites obtenues en concaténant une suite de $S(X)$ avec une suite de $S(Y)$. Par exemple, si $S(X)$ contient $[1, 3]$ et $S(Y)$ contient $[2, 4]$, alors $S(Z)$ contient $[1, 3, 2, 4]$.
• Si $Z$ est de la forme (X | Y), où $X$ et $Y$ sont ses sous-expressions gauche et droite, alors $S(Z) = S(X) \cup S(Y)$.

Différentes expressions valides peuvent représenter la même suite. Trouvez le nombre de suites distinctes représentées par au moins une expression valide. Comme la réponse peut être grande, affichez-la modulo $998\,244\,353$.

Entrée

L'entrée est constituée d'un seul cas de test au format suivant :

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

La première ligne contient un entier $N$ ($2 \le N \le 10^6$). La seconde ligne contient une chaîne $O$ composée de + et de | ($|O| = N - 1$).

Sortie

Affichez le nombre de suites distinctes pouvant être représentées, modulo $998\,244\,353$.

Exemples

Entrée 1

4
+|+

Sortie 1

4

Entrée 2

7
||+|||

Sortie 2

17

Entrée 3

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

Sortie 3

1774

Remarque

Pour le premier exemple, l'expression est [1]+[2]|[3]+[4].

Les cinq expressions valides suivantes peuvent être obtenues en ajoutant des parenthèses :

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

Les quatre suites distinctes suivantes sont représentées par au moins l'une de ces expressions valides :

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

Par conséquent, la réponse est $4$.