配点 : 500 点
問題文
乌龟喜欢玩绳子。今天是一个空字符串 准备 s 并执行以下操作。 我做了 N 次。
- s 作为字符串
分成 l,r 。
替换为 s 输出为 l\ +
()+\ r 。
N 操作后 s 的值为 T ,这样我们就可以计算出可能的操作方法的数量。 除以 998244353 求余数。
然而,一些正整数 k\ (1 \le k \le N) 存在 k 在第次操作中 (l,r) 对不同,只有这样 2 我们认为这两种操作方法是不同的。
还有,乌龟君不会说谎,所以一定要 s=T 操作方法是 1 似乎存在一个。 仅给出 T 。 长度由
制約
- 1 \le N \le 10^5
- T 满足
(,)组成 2N 字符串 - 通过执行适当的操作, s=T 可以
入力
输入将以以下形式从标准输入给出。
N T
出力
打印答案。
入力例 1
3 (())()
出力例 1
3
可以进行以下操作。 令
1 回目、 l,r 为空字符串。 s= () 变为。
2 回目、 l= () ,r 为空字符串。 s= ()() 变为。
3 回目、 l= ( ,r= )() 。 s= (())() 变为。
入力例 2
1 ()
出力例 2
1
入力例 3
7 (()(()(())()))
出力例 3
72
原案: 海龟0123__ 长度由小于