ศาสตราจารย์ 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$ คืออักขระตัวที่ $i$ ของสตริงข้อมูลนำเข้า $O$ และถูกใช้เป็นตัวดำเนินการระหว่าง $[i]$ กับ $[i + 1]$

เนื่องจากไม่ได้กำหนดลำดับความสำคัญของตัวดำเนินการ เราจึงพิจารณาทุกวิธีที่เป็นไปได้ในการใส่วงเล็บให้นิพจน์นี้อย่างสมบูรณ์โดยไม่เปลี่ยนลำดับของตัวถูกดำเนินการหรือตัวดำเนินการ นิพจน์แต่ละอันที่ได้จากวิธีนี้จะเรียกว่า นิพจน์ที่ถูกต้อง

สำหรับแต่ละนิพจน์ $Z$ ให้ $S(Z)$ แทนเซตของลำดับที่ถูกแทนด้วย $Z$ เซต $S(Z)$ ถูกนิยามแบบเวียนเกิดดังนี้:

• ถ้า $Z$ มีรูปแบบ [i] สำหรับบางค่าของ $i$ ($1 \le i \le N$) แล้ว $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]

เราสามารถใส่วงเล็บเพื่อให้ได้นิพจน์ที่ถูกต้อง $5$ แบบดังต่อไปนี้:

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

ลำดับที่แตกต่างกัน $4$ ลำดับต่อไปนี้ถูกแทนด้วยนิพจน์ที่ถูกต้องเหล่านี้อย่างน้อยหนึ่งนิพจน์:

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

ดังนั้น คำตอบคือ $4$