Профессор 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$.