問題文

整数 $N, K$ および、(,) からなる長さ $K$ の正しい括弧列 $S$ が与えられます。

(,) からなる長さ $N$ の文字列 $T$ のうち、以下の条件を全て満たすものの数を $998244353$ で割った余りを求めてください。

• $T$ の部分列であって、長さ $K$ の正しい括弧列であるものが存在する
• $T$ の部分列であって、長さ $K$ の正しい括弧列であるもののうち、辞書順で最小のものは $S$ である

なお、(,) からなる文字列の辞書順について、( は ) より小さい文字であるものとします。

また、正しい括弧列とは、 () である部分文字列を削除することを $0$ 回以上繰り返して空文字列にできる文字列を指します。

制約

• $K\leq N\leq\boldsymbol{\textcolor{FF0000}{10^{18}}}$
• $2\leq K\leq 5\times 10^{5}$
• $N, K$ は整数
• $S$ は (,) からなる長さ $K$ の正しい括弧列

入力

$N\ K$
$S$

出力

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

サンプル

7 4
(())

64

1000000000000000000 28
(()()(()))(()((()))())()(())

118659188