問題文

かめ君は、文字列で遊ぶのが好きです。今日は、空文字列 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 にすることが可能

入力例 1

3
(())()

出力例 1

3

以下のような操作が考えられます。

1 回目、 l,r を空文字列 とする。 s= () となる。

2 回目、 l= () ,r を空文字列 とする。 s= ()() となる。

3 回目、 l= ( ,r= )() とする。 s= (())() となる。

入力例 2

1
()

出力例 2

1

入力例 3

7
(()(()(())()))

出力例 3

72

原案: turtle0123__