Profesor JAG, badacz ciągów, opracowuje nowy język wyrażeń. Dane są liczba całkowita $N$ oraz napis $O = O_1 O_2 \cdots O_{N-1}$ składający się ze znaków + oraz |. W całym zadaniu ciąg o elementach $a_1, a_2, \ldots, a_k$ oznaczamy przez $[a_1, a_2, \ldots, a_k]$.

Rozważmy następujące wyrażenie:

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

Tutaj $O_i$ jest $i$-tym znakiem napisu wejściowego $O$ i pełni rolę operatora pomiędzy $[i]$ a $[i + 1]$.

Ponieważ priorytety operatorów nie są zdefiniowane, rozważamy wszystkie możliwe sposoby pełnego nawiasowania tego wyrażenia bez zmiany kolejności jego argumentów ani operatorów. Każde wyrażenie otrzymane w ten sposób nazywamy poprawnym wyrażeniem.

Dla każdego wyrażenia $Z$ niech $S(Z)$ oznacza zbiór ciągów reprezentowanych przez $Z$. Zbiór $S(Z)$ definiujemy rekurencyjnie w następujący sposób:

• Jeśli $Z$ ma postać [i] dla pewnego $i$ ($1 \le i \le N$), to $S(Z)$ składa się wyłącznie z jednoelementowego ciągu $[i]$.
• Jeśli $Z$ ma postać (X + Y), gdzie $X$ i $Y$ są odpowiednio jego lewym i prawym podwyrażeniem, to $S(Z)$ składa się ze wszystkich ciągów powstałych przez konkatenację pewnego ciągu z $S(X)$ z pewnym ciągiem z $S(Y)$. Na przykład jeśli $S(X)$ zawiera $[1, 3]$, a $S(Y)$ zawiera $[2, 4]$, to $S(Z)$ zawiera $[1, 3, 2, 4]$.
• Jeśli $Z$ ma postać (X | Y), gdzie $X$ i $Y$ są odpowiednio jego lewym i prawym podwyrażeniem, to $S(Z) = S(X) \cup S(Y)$.

Różne poprawne wyrażenia mogą reprezentować ten sam ciąg. Wyznacz liczbę różnych ciągów reprezentowanych przez co najmniej jedno poprawne wyrażenie. Ponieważ odpowiedź może być duża, wypisz ją modulo $998\,244\,353$.

Wejście

Wejście składa się z pojedynczego przypadku testowego w następującym formacie:

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

Pierwszy wiersz zawiera liczbę całkowitą $N$ ($2 \le N \le 10^6$). Drugi wiersz zawiera napis $O$ składający się ze znaków + oraz | ($|O| = N - 1$).

Wyjście

Wypisz liczbę różnych ciągów, które mogą zostać reprezentowane, modulo $998\,244\,353$.

Przykład

Wejście 1

4
+|+

Wyjście 1

4

Wejście 2

7
||+|||

Wyjście 2

17

Wejście 3

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

Wyjście 3

1774

Uwagi

Dla pierwszego przykładu wyrażenie ma postać [1]+[2]|[3]+[4].

Poprzez dodanie nawiasów można otrzymać następujących pięć poprawnych wyrażeń:

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

Następujące cztery różne ciągi są reprezentowane przez co najmniej jedno z tych poprawnych wyrażeń:

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

Zatem odpowiedź wynosi $4$.