Lukujonojen tutkija professori JAG kehittää uutta lausekekieltä. Sinulle annetaan kokonaisluku $N$ sekä merkkijono $O = O_1 O_2 \cdots O_{N-1}$, joka koostuu merkeistä + ja |. Koko tässä tehtävässä lukujonoa, jonka alkiot ovat $a_1, a_2, \ldots, a_k$, merkitään $[a_1, a_2, \ldots, a_k]$.

Tarkastellaan seuraavaa lauseketta:

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

Tässä $O_i$ on syötemerkkijonon $O$ $i$:s merkki, ja sitä käytetään operaattorina $[i]$:n ja $[i + 1]$:n välissä.

Koska operaattorien laskujärjestystä ei ole määritelty, tarkastelemme kaikkia mahdollisia tapoja suluttaa tämä lauseke täydellisesti muuttamatta operandien tai operaattorien järjestystä. Jokaista tällä tavoin saatua lauseketta kutsutaan kelvolliseksi lausekkeeksi.

Olkoon jokaiselle lausekkeelle $Z$ joukko $S(Z)$ niiden lukujonojen joukko, joita $Z$ esittää. Joukko $S(Z)$ määritellään rekursiivisesti seuraavasti:

• Jos $Z$ on muotoa [i] jollekin $i$ ($1 \le i \le N$), niin $S(Z)$ koostuu vain yksialkioisesta lukujonosta $[i]$.
• Jos $Z$ on muotoa (X + Y), missä $X$ ja $Y$ ovat sen vasen ja oikea alilauseke, niin $S(Z)$ koostuu kaikista lukujonoista, jotka saadaan yhdistämällä peräkkäin jokin joukon $S(X)$ lukujono ja jokin joukon $S(Y)$ lukujono. Esimerkiksi jos $S(X)$ sisältää lukujonon $[1, 3]$ ja $S(Y)$ sisältää lukujonon $[2, 4]$, niin $S(Z)$ sisältää lukujonon $[1, 3, 2, 4]$.
• Jos $Z$ on muotoa (X | Y), missä $X$ ja $Y$ ovat sen vasen ja oikea alilauseke, niin $S(Z) = S(X) \cup S(Y)$.

Eri kelvolliset lausekkeet voivat esittää samaa lukujonoa. Selvitä, kuinka monta eri lukujonoa vähintään yksi kelvollinen lauseke esittää. Koska vastaus voi olla suuri, tulosta se modulo $998\,244\,353$.

Syöte

Syöte koostuu yhdestä testitapauksesta seuraavassa muodossa:

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

Ensimmäinen rivi sisältää kokonaisluvun $N$ ($2 \le N \le 10^6$). Toinen rivi sisältää merkkijonon $O$, joka koostuu merkeistä + ja | ($|O| = N - 1$).

Tuloste

Tulosta esitettävissä olevien eri lukujonojen lukumäärä modulo $998\,244\,353$.

Esimerkit

Syöte 1

4
+|+

Tuloste 1

4

Syöte 2

7
||+|||

Tuloste 2

17

Syöte 3

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

Tuloste 3

1774

Selitys

Ensimmäisessä esimerkissä lauseke on [1]+[2]|[3]+[4].

Lisäämällä sulkeet voidaan saada seuraavat viisi kelvollista lauseketta:

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

Seuraavat neljä eri lukujonoa ovat vähintään yhden tällaisen kelvollisen lausekkeen esittämiä:

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

Siispä vastaus on $4$.