Profesor JAG, seorang peneliti barisan, sedang mengembangkan bahasa ekspresi baru. Anda diberikan sebuah bilangan bulat $N$ dan sebuah string $O = O_1 O_2 \cdots O_{N-1}$ yang terdiri dari + dan |. Di sepanjang soal ini, sebuah barisan dengan elemen-elemen $a_1, a_2, \ldots, a_k$ dinyatakan dengan $[a_1, a_2, \ldots, a_k]$.

Perhatikan ekspresi berikut:

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

Di sini, $O_i$ adalah karakter ke-$i$ dari string masukan $O$ dan digunakan sebagai operator di antara $[i]$ dan $[i + 1]$.

Karena prioritas operator tidak didefinisikan, kita meninjau semua cara yang mungkin untuk memberi tanda kurung secara lengkap pada ekspresi ini tanpa mengubah urutan operan maupun operatornya. Setiap ekspresi yang diperoleh dengan cara ini disebut ekspresi valid.

Untuk setiap ekspresi $Z$, misalkan $S(Z)$ menyatakan himpunan barisan yang direpresentasikan oleh $Z$. Himpunan $S(Z)$ didefinisikan secara rekursif sebagai berikut.

• Jika $Z$ berbentuk [i] untuk suatu $i$ ($1 \le i \le N$), maka $S(Z)$ hanya terdiri dari barisan satu elemen $[i]$.
• Jika $Z$ berbentuk (X + Y), dengan $X$ dan $Y$ adalah subekspresi kiri dan kanannya, maka $S(Z)$ terdiri dari setiap barisan yang diperoleh dengan menggabungkan suatu barisan di $S(X)$ dengan suatu barisan di $S(Y)$. Sebagai contoh, jika $S(X)$ memuat $[1, 3]$ dan $S(Y)$ memuat $[2, 4]$, maka $S(Z)$ memuat $[1, 3, 2, 4]$.
• Jika $Z$ berbentuk (X | Y), dengan $X$ dan $Y$ adalah subekspresi kiri dan kanannya, maka $S(Z) = S(X) \cup S(Y)$.

Ekspresi valid yang berbeda dapat merepresentasikan barisan yang sama. Carilah banyaknya barisan berbeda yang direpresentasikan oleh setidaknya satu ekspresi valid. Karena jawabannya bisa sangat besar, keluarkan hasilnya dalam modulo $998\,244\,353$.

Masukan

Masukan terdiri dari satu kasus uji dalam format berikut.

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

Baris pertama berisi sebuah bilangan bulat $N$ ($2 \le N \le 10^6$). Baris kedua berisi sebuah string $O$ yang terdiri dari + dan | ($|O| = N - 1$).

Keluaran

Keluarkan banyaknya barisan berbeda yang dapat direpresentasikan, dalam modulo $998\,244\,353$.

Contoh

Masukan 1

4
+|+

Keluaran 1

4

Masukan 2

7
||+|||

Keluaran 2

17

Masukan 3

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

Keluaran 3

1774

Catatan

Untuk contoh pertama, ekspresinya adalah [1]+[2]|[3]+[4].

Lima ekspresi valid berikut dapat diperoleh dengan menambahkan tanda kurung:

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

Empat barisan berbeda berikut direpresentasikan oleh setidaknya satu dari ekspresi-ekspresi valid tersebut:

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

Oleh karena itu, jawabannya adalah $4$.