数列の研究者である 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$ に対して、$Z$ によって表される数列の集合を $S(Z)$ とします。集合 $S(Z)$ は再帰的に次のように定義されます。

• $Z$ が（ある $i$ ($1 \le i \le N$) に対して）[i] の形をしているとき、$S(Z)$ は $1$ 要素の数列 $[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)$ です。

異なる有効な式が同じ数列を表すことがあります。少なくとも $1$ つの有効な式によって表される相異なる数列の個数を求めてください。答えは非常に大きくなる可能性があるため、$998\,244\,353$ で割った余りを出力してください。

入力

入力は以下の形式の単一のテストケースからなります。

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

$1$ 行目には整数 $N$ ($2 \le N \le 10^6$) が与えられます。$2$ 行目には + と | からなる文字列 $O$ ($|O| = N - 1$) が与えられます。

出力

表すことができる相異なる数列の個数を $998\,244\,353$ で割った余りを出力してください。

入出力例

入力 1

4
+|+

出力 1

4

入力 2

7
||+|||

出力 2

17

入力 3

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

出力 3

1774

注記

最初の入出力例では、式は [1]+[2]|[3]+[4] です。

括弧を付けることで、以下の $5$ つの有効な式が得られます。

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

以下の $4$ つの相異なる数列が、これらの有効な式のうち少なくとも $1$ つによって表されます。

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

したがって、答えは $4$ です。