Giáo sư JAG, một nhà nghiên cứu về dãy số, đang phát triển một ngôn ngữ biểu thức mới. Bạn được cho một số nguyên $N$ và một xâu $O = O_1 O_2 \cdots O_{N-1}$ chỉ gồm các ký tự + và |. Trong suốt bài toán này, một dãy số gồm các phần tử $a_1, a_2, \ldots, a_k$ được ký hiệu là $[a_1, a_2, \ldots, a_k]$.

Xét biểu thức sau:

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

Ở đây, $O_i$ là ký tự thứ $i$ của xâu đầu vào $O$ và được dùng làm toán tử giữa $[i]$ và $[i + 1]$.

Vì thứ tự ưu tiên của các toán tử không được định nghĩa, ta xét tất cả các cách đặt ngoặc đầy đủ cho biểu thức này mà không làm thay đổi thứ tự của các toán hạng hay toán tử. Mỗi biểu thức thu được theo cách này được gọi là một biểu thức hợp lệ.

Với mỗi biểu thức $Z$, gọi $S(Z)$ là tập hợp các dãy số được biểu diễn bởi $Z$. Tập hợp $S(Z)$ được định nghĩa đệ quy như sau:

• Nếu $Z$ có dạng [i] với một số $i$ nào đó ($1 \le i \le N$), thì $S(Z)$ chỉ gồm duy nhất dãy số một phần tử $[i]$.
• Nếu $Z$ có dạng (X + Y), trong đó $X$ và $Y$ lần lượt là biểu thức con bên trái và bên phải của nó, thì $S(Z)$ gồm mọi dãy số thu được bằng cách nối một dãy số trong $S(X)$ với một dãy số trong $S(Y)$. Ví dụ, nếu $S(X)$ chứa $[1, 3]$ và $S(Y)$ chứa $[2, 4]$, thì $S(Z)$ chứa $[1, 3, 2, 4]$.
• Nếu $Z$ có dạng (X | Y), trong đó $X$ và $Y$ lần lượt là biểu thức con bên trái và bên phải của nó, thì $S(Z) = S(X) \cup S(Y)$.

Các biểu thức hợp lệ khác nhau có thể biểu diễn cùng một dãy số. Hãy tìm số lượng dãy số phân biệt được biểu diễn bởi ít nhất một biểu thức hợp lệ. Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho $998\,244\,353$.

Dữ liệu vào

Dữ liệu vào gồm một bộ test duy nhất có định dạng như sau:

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

Dòng đầu tiên chứa một số nguyên $N$ ($2 \le N \le 10^6$). Dòng thứ hai chứa một xâu $O$ gồm các ký tự + và | ($|O| = N - 1$).

Dữ liệu ra

In ra số lượng dãy số phân biệt có thể được biểu diễn, lấy phần dư theo modulo $998\,244\,353$.

Ví dụ

Dữ liệu vào 1

4
+|+

Dữ liệu ra 1

4

Dữ liệu vào 2

7
||+|||

Dữ liệu ra 2

17

Dữ liệu vào 3

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

Dữ liệu ra 3

1774

Ghi chú

Ở ví dụ đầu tiên, biểu thức là [1]+[2]|[3]+[4].

Năm biểu thức hợp lệ sau đây có thể thu được bằng cách thêm dấu ngoặc:

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

Bốn dãy số phân biệt sau đây được biểu diễn bởi ít nhất một trong các biểu thức hợp lệ này:

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

Do đó, đáp án là $4$.