פרופסור 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].

ניתן לקבל את חמשת הביטויים התקינים הבאים על ידי הוספת סוגריים:

• ((([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$.