AT_abc312_d [ABC312D] Count Bracket Sequences

[problemUrl]: https://atcoder.jp/contests/abc312/tasks/abc312_d 空でない文字列 $ S $ が与えられます。$ S $ の各文字は `(`, `)`, `?` のいずれかです。 $ S $ に含まれる `?` の個数を $ x $ とすると、`?` を `(` あるいは `)` に置き換えて新しい文字列を作る方法は $ 2^x $ 通りありますが、このうち新しくできた文字列が**括弧列**となるような置き換え方の数を $ 998244353 $ で割った余りを求めてください。 ただし、括弧列とは以下のいずれかの条件を満たす文字列のことです。 - 空文字列 - ある括弧列 $ A $ が存在して、`(`, $ A $, `)` をこの順に連結した文字列 - ある空でない括弧列 $ A,\ B $ が存在して、$ A,\ B $ をこの順に連結した文字列

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

答えを出力せよ。

### 制約 - $ S $ は長さ $ 3000 $ 以下の `(`, `)`, `?` からなる空でない文字列 ### Sample Explanation 1 $ S $ を `()()()` あるいは `(())()` に置き換えると括弧列となります。 他の置き換え方で新しくできた文字列が括弧列となることはないので、$ 2 $ を出力します。 ### Sample Explanation 3 $ 998244353 $ で割った余りを出力してください。