Professor JAG, en forsker på følger, utvikler et nytt uttrykksspråk. Du får gitt et heltall $N$ og en streng $O = O_1 O_2 \cdots O_{N-1}$ som består av + og |. Gjennom hele denne oppgaven betegnes en følge med elementene $a_1, a_2, \ldots, a_k$ som $[a_1, a_2, \ldots, a_k]$.

Betrakt følgende uttrykk:

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

Her er $O_i$ det $i$-te tegnet i inndatastrengen $O$ og brukes som operatoren mellom $[i]$ og $[i + 1]$.

Siden operatorpresedens ikke er definert, betrakter vi alle mulige måter å sette fullstendige parenteser i dette uttrykket på uten å endre rekkefølgen på operandene eller operatorene. Hvert uttrykk som oppnås på denne måten, kalles et gyldig uttrykk.

For hvert uttrykk $Z$, la $S(Z)$ betegne mengden av følger som representeres av $Z$. Mengden $S(Z)$ er definert rekursivt som følger:

• Hvis $Z$ har formen [i] for en $i$ ($1 \le i \le N$), så består $S(Z)$ kun av énelementfølgen $[i]$.
• Hvis $Z$ har formen (X + Y), der $X$ og $Y$ er henholdsvis venstre og høyre deluttrykk, så består $S(Z)$ av enhver følge som oppnås ved å konkatenerere en følge i $S(X)$ med en følge i $S(Y)$. For eksempel, hvis $S(X)$ inneholder $[1, 3]$ og $S(Y)$ inneholder $[2, 4]$, så inneholder $S(Z)$ følgen $[1, 3, 2, 4]$.
• Hvis $Z$ har formen (X | Y), der $X$ og $Y$ er henholdsvis venstre og høyre deluttrykk, så er $S(Z) = S(X) \cup S(Y)$.

Ulike gyldige uttrykk kan representere den samme følgen. Finn antall distinkte følger som representeres av minst ett gyldig uttrykk. Siden svaret kan bli stort, skal du skrive det ut modulo $998\,244\,353$.

Inndata

Inndataene består av ett enkelt testtilfelle på følgende format:

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

Den første linjen inneholder et heltall $N$ ($2 \le N \le 10^6$). Den andre linjen inneholder en streng $O$ som består av + og | ($|O| = N - 1$).

Utdata

Skriv ut antall distinkte følger som kan representeres, modulo $998\,244\,353$.

Eksempler

Inndata 1

4
+|+

Utdata 1

4

Inndata 2

7
||+|||

Utdata 2

17

Inndata 3

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

Utdata 3

1774

Forklaring

For det første eksempelet er uttrykket [1]+[2]|[3]+[4].

Følgende fem gyldige uttrykk kan oppnås ved å legge til parenteser:

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

Følgende fire distinkte følger representeres av minst ett av disse gyldige uttrykkene:

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

Derfor er svaret $4$.