問題文

(,),? のみからなる文字列 $t$ が次の条件を満たすとき、$t$ は 良い文字列 であるとします。

• $t$ における ? のそれぞれを (,) のいずれかに適切に置き換えることで、正しい括弧列にできる。

例えば、$t=$ ?(?) は ? の置き換えにより (()) とできるため、良い文字列です。
同様に、$t=$ ???? や $t=$ ()()() も良い文字列です（必ずしも $t$ に ? が含まれている必要はありません）。
一方、$t=$ )??? は ? をどのように置き換えても正しい括弧列にはならないため、良い文字列ではありません。

(,),?,. のみからなる文字列 $s$ が与えられます。
$s$ における . のそれぞれを (,),? のいずれかに置き換えることで得られるような良い文字列は何通りあるでしょうか。
答えは非常に大きくなることがあるので、$998244353$ で割った余りを求めてください。

補足

1. 空文字列は正しい括弧列である。
2. 文字列 $A$ が正しい括弧列であるとき、($,A,$ ) をこの順に並べた文字列も正しい括弧列である。
3. 空でない文字列 $A,B$ が正しい括弧列であるとき、$A,B$ をこの順に並べた文字列も正しい括弧列である。
4. 上記1~3のいずれかの条件を満たす文字列のみが正しい括弧列である。

制約

• $s$ は (,),?,. のみからなる文字列である。
• $1\le |s|\le 4000$

入力

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

$s$

出力

$s$ における . のそれぞれを (,),? のいずれかに置き換えることで得られるような良い文字列の数を $998244353$ で割った余りを出力してください。

サンプル

..

4

((.?

2

(())

1

((()

0

(...)?..?.

358