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