AT_pakencamp_2024_day3_2_g Bracket Sequence

`(` または `)` のみからなる文字列 $ S $ が与えられます。以下の問題を解いてください。 - $ 0 $ で初期化された変数 $ x $ と、長さ $ 0 $ の数列 $ h $ がある。以下の操作を $ 0 $ 回以上好きな回数行う。 - $ h $ に $ x $ を追加する。その後、以下のどちらかを行う。 - $ x $ を $ x+1 $ で置き換える。 - $ S $ の $ x+1 $ 文字目から $ y $ 文字目までを取り出した文字列が正規括弧列であるような $ y $ を好きに選び、 $ x $ を $ y $ で置き換える。この操作は $ x\leq |S|-1 $ のときのみ行うことができる。 - 操作を終了したときに $ x=|S| $ となっているとき、最終的な $ h $ としてありうるものの個数を $ 998244353 $ で割ったあまりを求めよ。 正規括弧列とは？正規括弧列とは、`()` である部分文字列を削除することを $ 0 $ 回以上繰り返して空文字列にできる文字列を指します。

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

答えを出力せよ。

### Sample Explanation 1 最終的な $ h $ としてありうるものは以下の $ 6 $ 通りです。 - $ (0) $ - $ (0,1,5) $ - $ (0,1,3,5) $ - $ (0,1,3,4,5) $ - $ (0,1,2,3,5) $ - $ (0,1,2,3,4,5) $ ### Constraints - $ S $ は `(` または `)` のみからなる長さ $ 1 $ 以上 $ 200000 $ 以下の文字列