AT_pakencamp_2021_day2_k Bracket Inserting

[problemUrl]: https://atcoder.jp/contests/pakencamp-2021-day2/tasks/pakencamp_2021_day2_k かめ君は、文字列で遊ぶのが好きです。今日は、空文字列 $ 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 $ のみが与えられます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ T $

答えを出力せよ。

### 制約 - $ 1\ \le\ N\ \le\ 10^5 $ - $ T $ は `(`, `)` からなる長さ $ 2N $ の文字列 - 適切な操作をすることで、必ず $ s=T $ にすることが可能 ### Sample Explanation 1 以下のような操作が考えられます。 $ 1 $ 回目、 $ l,r $ を空文字列 とする。 $ s= $ `()` となる。 $ 2 $ 回目、 $ l= $ `()` $ ,r $ を空文字列 とする。 $ s= $ `()()` となる。 $ 3 $ 回目、 $ l= $ `(` $ ,r= $ ` )()` とする。 $ s= $ `(())()` となる。 ### Sample Explanation 3 原案: \[turtle0123\\\_\\\_\](https://atcoder.jp/users/turtle0123\_\_)