Professor JAG, en forskare inom talföljder, håller på att utveckla ett nytt uttrycksspråk. Du får ett heltal $N$ och en sträng $O = O_1 O_2 \cdots O_{N-1}$ som består av + och |. Genom hela detta problem betecknas en talföljd med elementen $a_1, a_2, \ldots, a_k$ som $[a_1, a_2, \ldots, a_k]$.

Betrakta följande uttryck:

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

Här är $O_i$ det $i$:te tecknet i indatasträngen $O$ och används som operator mellan $[i]$ och $[i + 1]$.

Eftersom operatorprioritet inte är definierad betraktar vi alla möjliga sätt att fullständigt parentesera detta uttryck utan att ändra ordningen på dess operander eller operatorer. Varje uttryck som erhålls på detta sätt kallas ett giltigt uttryck.

För varje uttryck $Z$, låt $S(Z)$ beteckna mängden av talföljder som representeras av $Z$. Mängden $S(Z)$ definieras rekursivt enligt följande:

• Om $Z$ har formen [i] för något $i$ ($1 \le i \le N$), så består $S(Z)$ endast av talföljden med ett element $[i]$.
• Om $Z$ har formen (X + Y), där $X$ och $Y$ är dess vänstra respektive högra deluttryck, så består $S(Z)$ av varje talföljd som erhålls genom att konkatenera en talföljd i $S(X)$ med en talföljd i $S(Y)$. Till exempel, om $S(X)$ innehåller $[1, 3]$ och $S(Y)$ innehåller $[2, 4]$, så innehåller $S(Z)$ talföljden $[1, 3, 2, 4]$.
• Om $Z$ har formen (X | Y), där $X$ och $Y$ är dess vänstra respektive högra deluttryck, så är $S(Z) = S(X) \cup S(Y)$.

Olika giltiga uttryck kan representera samma talföljd. Bestäm antalet distinkta talföljder som representeras av minst ett giltigt uttryck. Eftersom svaret kan vara stort, skriv ut det modulo $998\,244\,353$.

Indata

Indatan består av ett enda testfall i följande format:

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

Den första raden innehåller ett heltal $N$ ($2 \le N \le 10^6$). Den andra raden innehåller en sträng $O$ som består av + och | ($|O| = N - 1$).

Utdata

Skriv ut antalet distinkta talföljder som kan representeras, modulo $998\,244\,353$.

Exempel

Indata 1

4
+|+

Utdata 1

4

Indata 2

7
||+|||

Utdata 2

17

Indata 3

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

Utdata 3

1774

Förklaring

För det första exemplet är uttrycket [1]+[2]|[3]+[4].

Följande fem giltiga uttryck kan erhållas genom att lägga till parenteser:

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

Följande fyra distinkta talföljder representeras av minst ett av dessa giltiga uttryck:

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

Därför är svaret $4$.