Professor JAG, ein Sequenzforscher, entwickelt eine neue Ausdruckssprache. Gegeben sind eine ganze Zahl $N$ und eine Zeichenkette $O = O_1 O_2 \cdots O_{N-1}$, die aus + und | besteht. In dieser gesamten Aufgabe wird eine Folge mit den Elementen $a_1, a_2, \ldots, a_k$ mit $[a_1, a_2, \ldots, a_k]$ bezeichnet.

Betrachte den folgenden Ausdruck:

$$[1]\ O_1\ [2]\ O_2\ \ldots\ O_{N-1}\ [N]$$

Hierbei ist $O_i$ das $i$-te Zeichen der Eingabezeichenkette $O$ und wird als Operator zwischen $[i]$ und $[i + 1]$ verwendet.

Da keine Operatorrangfolge definiert ist, betrachten wir alle möglichen Arten, diesen Ausdruck vollständig zu klammern, ohne die Reihenfolge seiner Operanden oder Operatoren zu verändern. Jeder auf diese Weise erhaltene Ausdruck wird als gültiger Ausdruck bezeichnet.

Für jeden Ausdruck $Z$ bezeichne $S(Z)$ die Menge der durch $Z$ dargestellten Folgen. Die Menge $S(Z)$ ist rekursiv wie folgt definiert:

• Hat $Z$ die Form [i] für ein $i$ ($1 \le i \le N$), so besteht $S(Z)$ nur aus der einelementigen Folge $[i]$.
• Hat $Z$ die Form (X + Y), wobei $X$ und $Y$ der linke bzw. rechte Teilausdruck sind, so besteht $S(Z)$ aus jeder Folge, die durch Verkettung einer Folge aus $S(X)$ mit einer Folge aus $S(Y)$ entsteht. Enthält beispielsweise $S(X)$ die Folge $[1, 3]$ und $S(Y)$ die Folge $[2, 4]$, so enthält $S(Z)$ die Folge $[1, 3, 2, 4]$.
• Hat $Z$ die Form (X | Y), wobei $X$ und $Y$ der linke bzw. rechte Teilausdruck sind, so gilt $S(Z) = S(X) \cup S(Y)$.

Verschiedene gültige Ausdrücke können dieselbe Folge darstellen. Bestimme die Anzahl der verschiedenen Folgen, die durch mindestens einen gültigen Ausdruck dargestellt werden. Da die Antwort sehr groß sein kann, gib sie modulo $998\,244\,353$ aus.

Eingabe

Die Eingabe besteht aus einem einzigen Testfall im folgenden Format:

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

Die erste Zeile enthält eine ganze Zahl $N$ ($2 \le N \le 10^6$). Die zweite Zeile enthält eine Zeichenkette $O$, die aus + und | besteht ($|O| = N - 1$).

Ausgabe

Gib die Anzahl der verschiedenen darstellbaren Folgen modulo $998\,244\,353$ aus.

Beispiele

Eingabe 1

4
+|+

Ausgabe 1

4

Eingabe 2

7
||+|||

Ausgabe 2

17

Eingabe 3

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

Ausgabe 3

1774

Hinweis

Für das erste Beispiel lautet der Ausdruck [1]+[2]|[3]+[4].

Durch Setzen von Klammern können die folgenden fünf gültigen Ausdrücke erhalten werden:

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

Die folgenden vier verschiedenen Folgen werden durch mindestens einen dieser gültigen Ausdrücke dargestellt:

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

Daher lautet die Antwort $4$.