D - Count Bracket Sequences Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

空でない文字列 S が与えられます。S の各文字は (, ), ? のいずれかです。
S に含まれる ? の個数を x とすると、?( あるいは ) に置き換えて新しい文字列を作る方法は 2^x 通りありますが、このうち新しくできた文字列が括弧列となるような置き換え方の数を 998244353 で割った余りを求めてください。

ただし、括弧列とは以下のいずれかの条件を満たす文字列のことです。

  • 空文字列
  • ある括弧列 A が存在して、(, A, ) をこの順に連結した文字列
  • ある空でない括弧列 A, B が存在して、A, B をこの順に連結した文字列

制約

  • S は長さ 3000 以下の (, ), ? からなる空でない文字列

入力

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

S

出力

答えを出力せよ。


入力例 1

(???(?

出力例 1

2

S()()() あるいは (())() に置き換えると括弧列となります。
他の置き換え方で新しくできた文字列が括弧列となることはないので、2 を出力します。


入力例 2

)))))

出力例 2

0

入力例 3

??????????????(????????(??????)?????????(?(??)

出力例 3

603032273

998244353 で割った余りを出力してください。

Score : 400 points

Problem Statement

You are given a non-empty string S consisting of (, ), and ?.
There are 2^x ways to obtain a new string by replacing each ? in S with ( and ), where x is the number of occurrences of ? in S. Among them, find the number, modulo 998244353, of ways that yield a parenthesis string.

A string is said to be a parenthesis string if one of the following conditions is satisfied.

  • It is an empty string.
  • It is a concatenation of (, A, and ), for some parenthesis string A.
  • It is a concatenation of A and B, for some non-empty parenthesis strings A and B.

Constraints

  • S is a non-empty string of length at most 3000 consisting of (, ), and ?.

Input

The input is given from Standard Input in the following format:

S

Output

Print the answer.


Sample Input 1

(???(?

Sample Output 1

2

Replacing S with ()()() or (())() yields a parenthesis string.
The other replacements do not yield a parenthesis string, so 2 should be printed.


Sample Input 2

)))))

Sample Output 2

0

Sample Input 3

??????????????(????????(??????)?????????(?(??)

Sample Output 3

603032273

Print the count modulo 998244353.