問題文

( または ) のみからなる文字列 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 で割ったあまりを求めよ。

制約

• S は ( または ) のみからなる長さ 1 以上 200000 以下の文字列

入力例 1

(()())

出力例 1

6

最終的な 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)