JAG prófessor, sem rannsakar runur, er að þróa nýtt segðamál. Gefin er heiltala $N$ og strengur $O = O_1 O_2 \cdots O_{N-1}$ sem samanstendur af + og |. Í öllu þessu verkefni er runa með stökum $a_1, a_2, \ldots, a_k$ táknuð með $[a_1, a_2, \ldots, a_k]$.

Lítum á eftirfarandi segð:

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

Hér er $O_i$ $i$-ti stafurinn í inntaksstrengnum $O$ og er notaður sem virki milli $[i]$ og $[i + 1]$.

Þar sem forgangsröð virkja er ekki skilgreind skoðum við allar mögulegar leiðir til að svigasetja þessa segð að fullu án þess að breyta röð þolenda eða virkja. Sérhver segð sem fæst með þessum hætti kallast gild segð.

Fyrir sérhverja segð $Z$, látum $S(Z)$ tákna mengi þeirra runa sem $Z$ táknar. Mengið $S(Z)$ er skilgreint endurkvæmt á eftirfarandi hátt:

• Ef $Z$ hefur formið [i] fyrir eitthvert $i$ ($1 \le i \le N$), þá samanstendur $S(Z)$ eingöngu af einstaksrununni $[i]$.
• Ef $Z$ hefur formið (X + Y), þar sem $X$ og $Y$ eru vinstri og hægri hlutsegðir hennar, þá samanstendur $S(Z)$ af sérhverri runu sem fæst með því að skeyta saman runu úr $S(X)$ og runu úr $S(Y)$. Til dæmis, ef $S(X)$ inniheldur $[1, 3]$ og $S(Y)$ inniheldur $[2, 4]$, þá inniheldur $S(Z)$ rununa $[1, 3, 2, 4]$.
• Ef $Z$ hefur formið (X | Y), þar sem $X$ og $Y$ eru vinstri og hægri hlutsegðir hennar, þá er $S(Z) = S(X) \cup S(Y)$.

Ólíkar gildar segðir geta táknað sömu rununa. Finnið fjölda ólíkra runa sem eru táknaðar með að minnsta kosti einni gildri segð. Þar sem svarið getur verið stórt skal prenta það módúló $998\,244\,353$.

Inntak

Inntakið samanstendur af einu prófunartilfelli á eftirfarandi sniði:

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

Fyrri línan inniheldur heiltölu $N$ ($2 \le N \le 10^6$). Seinni línan inniheldur streng $O$ sem samanstendur af + og | ($|O| = N - 1$).

Úttak

Prentið fjölda ólíkra runa sem hægt er að tákna, módúló $998\,244\,353$.

Dæmi

Inntak 1

4
+|+

Úttak 1

4

Inntak 2

7
||+|||

Úttak 2

17

Inntak 3

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

Úttak 3

1774

Skýring

Í fyrsta dæminu er segðin [1]+[2]|[3]+[4].

Eftirfarandi fimm gildu segðir fást með því að bæta við svigum:

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

Eftirfarandi fjórar ólíku runur eru táknaðar með að minnsta kosti einni af þessum gildu segðum:

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

Því er svarið $4$.