研究序列嘅 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$ 係輸入字串 $O$ 嘅第 $i$ 個字符，用嚟做 $[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$。