問題文

正しいカッコ列を、次の条件のいずれかを満たす文字列と定めます。

• 空文字列
• 正しいカッコ列 $A$ が存在して ( $A$ ) をこの順につなげたもの
• 空でない正しいカッコ列 $A, B$ が存在して $A, B$ をこの順につなげたもの

たとえば (())() は正しいカッコ列であり、 ()( や )( は正しいカッコ列ではありません。

正の偶数 $N$ に対して、長さ $N$ のA型の正しいカッコ列を次のように定めます。

• $1 \le i \le N/2$ に対し $S_i$ は (
• $N/2+1 \le i \le N$ に対し $S_i$ は )

たとえば、 (())、 ((((())))) は A型の正しいカッコ列です。

正の偶数 $N$ に対して、長さ $N$ のB型の正しいカッコ列を次のように定めます。

• $i$ が奇数のとき $S_i$ は (
• $i$ が偶数のとき $S_i$ は )

たとえば、 ()()、 ()()()()() は B型の正しいカッコ列です。

長さ $N$ の A型 または B型 の正しいカッコ列 $S$ が与えられます。$0, 1$ からなる長さ $N$ の列 $T$ であって、次の条件を満たすものの個数を求めてください。

• $T_i = 0$ となる整数 $i$ $(1\le i \le N)$ がある場合、$T_i = 0$ となる $i$ を昇順に $P_1, \cdots, P_k$ とする。 $S_{P_1}, \cdots, S_{P_k}$ を順につなげたものを $X$ とすると、 $X$ は正しいカッコ列である。
• $T_i = 1$ となる整数 $i$ $(1\le i \le N)$ がある場合、$T_i = 1$ となる $i$ を昇順に $Q_1, \cdots, Q_l$ とする。 $S_{Q_1}, \cdots, S_{Q_l}$ を順につなげたものを $Y$ とすると、 $Y$ は正しいカッコ列である。

ただし、答えは非常に大きくなる場合があるため、 $998244353$ で割った余りを出力してください。

制約

• $2 \le N \le 5\times 10^5$
• $N$ は偶数である
• $S$ は A型 または B型 の正しいカッコ列である

入力

$N$
$S$

出力

答えを出力してください。

サンプル

4
(())

6

4
()()

4

2
()

2

40
(((((((((((((((((((())))))))))))))))))))

88808106