Il professor JAG, uno studioso di successioni, sta sviluppando un nuovo linguaggio di espressioni. Ti vengono dati un intero $N$ e una stringa $O = O_1 O_2 \cdots O_{N-1}$ composta da + e |. In tutto questo problema, una sequenza con elementi $a_1, a_2, \ldots, a_k$ è indicata con $[a_1, a_2, \ldots, a_k]$.

Considera la seguente espressione:

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

Qui, $O_i$ è l'$i$-esimo carattere della stringa di input $O$ ed è usato come operatore tra $[i]$ e $[i + 1]$.

Poiché la precedenza degli operatori non è definita, consideriamo tutti i modi possibili di parentesizzare completamente questa espressione senza cambiare l'ordine dei suoi operandi o operatori. Ogni espressione ottenuta in questo modo è chiamata un'espressione valida.

Per ogni espressione $Z$, sia $S(Z)$ l'insieme delle sequenze rappresentate da $Z$. L'insieme $S(Z)$ è definito ricorsivamente come segue:

• Se $Z$ ha la forma [i] per qualche $i$ ($1 \le i \le N$), allora $S(Z)$ consiste solo della sequenza di un elemento $[i]$.
• Se $Z$ ha la forma (X + Y), dove $X$ e $Y$ sono le sue sottoespressioni sinistra e destra, allora $S(Z)$ consiste di ogni sequenza ottenuta concatenando una sequenza in $S(X)$ con una sequenza in $S(Y)$. Ad esempio, se $S(X)$ contiene $[1, 3]$ e $S(Y)$ contiene $[2, 4]$, allora $S(Z)$ contiene $[1, 3, 2, 4]$.
• Se $Z$ ha la forma (X | Y), dove $X$ e $Y$ sono le sue sottoespressioni sinistra e destra, allora $S(Z) = S(X) \cup S(Y)$.

Espressioni valide diverse possono rappresentare la stessa sequenza. Trova il numero di sequenze distinte rappresentate da almeno un'espressione valida. Poiché la risposta può essere molto grande, stampala modulo $998\,244\,353$.

Input

L'input è composto da un singolo caso di test nel seguente formato:

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

La prima riga contiene un intero $N$ ($2 \le N \le 10^6$). La seconda riga contiene una stringa $O$ composta da + e | ($|O| = N - 1$).

Output

Stampa il numero di sequenze distinte che possono essere rappresentate, modulo $998\,244\,353$.

Esempi

Input 1

4
+|+

Output 1

4

Input 2

7
||+|||

Output 2

17

Input 3

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

Output 3

1774

Note

Per il primo esempio, l'espressione è [1]+[2]|[3]+[4].

Aggiungendo le parentesi si possono ottenere le seguenti cinque espressioni valide:

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

Le seguenti quattro sequenze distinte sono rappresentate da almeno una di queste espressioni valide:

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

Pertanto, la risposta è $4$.