Тізбектерді зерттеуші профессор JAG жаңа өрнектер тілін жасап жатыр. Сізге бүтін $N$ саны және + пен | таңбаларынан тұратын $O = O_1 O_2 \cdots O_{N-1}$ жолы берілген. Осы есептің өн бойында элементтері $a_1, a_2, \ldots, a_k$ болатын тізбек $[a_1, a_2, \ldots, a_k]$ деп белгіленеді.

Келесі өрнекті қарастырайық:

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

Мұндағы $O_i$ — кіріс $O$ жолының $i$-ші таңбасы және ол $[i]$ мен $[i + 1]$ арасындағы оператор ретінде қолданылады.

Операторлардың басымдылығы анықталмағандықтан, біз операндтар мен операторлардың ретін өзгертпей, осы өрнекке толықтай жақша қоюдың барлық мүмкін тәсілдерін қарастырамыз. Осылайша алынған әрбір өрнек дұрыс өрнек деп аталады.

Әрбір $Z$ өрнегі үшін $S(Z)$ арқылы $Z$ өрнегі сипаттайтын тізбектер жиынын белгілейік. $S(Z)$ жиыны рекурсивті түрде келесідей анықталады:

• Егер $Z$ өрнегі қандай да бір $i$ ($1 \le i \le N$) үшін [i] түрінде болса, онда $S(Z)$ тек бір элементті $[i]$ тізбегінен тұрады.
• Егер $Z$ өрнегі (X + Y) түрінде болса, мұндағы $X$ пен $Y$ — оның сол және оң жақ ішкі өрнектері, онда $S(Z)$ жиыны $S(X)$ жиынындағы тізбекті $S(Y)$ жиынындағы тізбекпен тіркестіру (конкатенациялау) арқылы алынатын барлық тізбектерден тұрады. Мысалы, егер $S(X)$ жиынында $[1, 3]$ болса және $S(Y)$ жиынында $[2, 4]$ болса, онда $S(Z)$ жиынында $[1, 3, 2, 4]$ болады.
• Егер $Z$ өрнегі (X | Y) түрінде болса, мұндағы $X$ пен $Y$ — оның сол және оң жақ ішкі өрнектері, онда $S(Z) = S(X) \cup S(Y)$.

Әртүрлі дұрыс өрнектер бірдей тізбекті сипаттауы мүмкін. Кемінде бір дұрыс өрнек арқылы сипатталатын әртүрлі тізбектердің санын табыңыз. Жауап өте үлкен болуы мүмкін болғандықтан, оны $998\,244\,353$ санына бөлгендегі қалдықпен шығарыңыз.

Кіріс деректері

Кіріс деректері келесі форматтағы бір тесттен тұрады:

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

Бірінші жолда бүтін $N$ саны ($2 \le N \le 10^6$) берілген. Екінші жолда + және | таңбаларынан тұратын $O$ жолы ($|O| = N - 1$) берілген.

Шығыс деректері

Сипаттауға болатын әртүрлі тізбектердің санын $998\,244\,353$ модулі бойынша шығарыңыз.

Мысалдар

Кіріс деректері 1

4
+|+

Шығыс деректері 1

4

Кіріс деректері 2

7
||+|||

Шығыс деректері 2

17

Кіріс деректері 3

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

Шығыс деректері 3

1774

Ескертпе

Бірінші мысал үшін өрнек [1]+[2]|[3]+[4] болып табылады.

Жақшаларды қою арқылы келесі бес дұрыс өрнекті алуға болады:

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

Келесі төрт әртүрлі тізбек осы дұрыс өрнектердің кемінде біреуімен сипатталады:

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

Демек, жауабы — $4$.