序列研究者 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$。