يقوم الأستاذ 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$.