Професор JAG, дослідник послідовностей, розробляє нову мову виразів. Вам дано ціле число $N$ та рядок $O = O_1 O_2 \cdots O_{N-1}$, що складається із символів + та |. Протягом усієї задачі послідовність з елементами $a_1, a_2, \ldots, a_k$ позначається як $[a_1, a_2, \ldots, a_k]$.

Розглянемо такий вираз:

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

Тут $O_i$ — $i$-й символ вхідного рядка $O$, який використовується як оператор між $[i]$ та $[i + 1]$.

Оскільки пріоритет операторів не визначено, ми розглядаємо всі можливі способи повністю розставити дужки в цьому виразі, не змінюючи порядок операндів та операторів. Кожен отриманий у такий спосіб вираз називається коректним виразом.

Для кожного виразу $Z$ позначимо через $S(Z)$ множину послідовностей, які задаються виразом $Z$. Множина $S(Z)$ визначається рекурсивно таким чином:

• Якщо $Z$ має вигляд [i] для деякого $i$ ($1 \le i \le N$), то $S(Z)$ складається лише з одноелементної послідовності $[i]$.
• Якщо $Z$ має вигляд (X + Y), де $X$ і $Y$ — його лівий і правий підвирази, то $S(Z)$ складається з усіх послідовностей, які отримуються конкатенацією деякої послідовності з $S(X)$ та деякої послідовності з $S(Y)$. Наприклад, якщо $S(X)$ містить $[1, 3]$, а $S(Y)$ містить $[2, 4]$, то $S(Z)$ містить $[1, 3, 2, 4]$.
• Якщо $Z$ має вигляд (X | Y), де $X$ і $Y$ — його лівий і правий підвирази, то $S(Z) = S(X) \cup S(Y)$.

Різні коректні вирази можуть задавати одну й ту саму послідовність. Знайдіть кількість різних послідовностей, що задаються принаймні одним коректним виразом. Оскільки відповідь може бути великою, виведіть її за модулем $998\,244\,353$.

Вхідні дані

Вхідні дані складаються з одного тестового випадку в такому форматі:

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

Перший рядок містить ціле число $N$ ($2 \le N \le 10^6$). Другий рядок містить рядок $O$, що складається із символів + та | ($|O| = N - 1$).

Вихідні дані

Виведіть кількість різних послідовностей, які можуть бути представлені, за модулем $998\,244\,353$.

Приклади

Вхідні дані 1

4
+|+

Вихідні дані 1

4

Вхідні дані 2

7
||+|||

Вихідні дані 2

17

Вхідні дані 3

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

Вихідні дані 3

1774

Примітка

У першому прикладі вираз має вигляд [1]+[2]|[3]+[4].

Додаванням дужок можна отримати такі п'ять коректних виразів:

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

Такі чотири різні послідовності задаються принаймні одним із цих коректних виразів:

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

Отже, відповідь дорівнює $4$.