/ 
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.