問題

()^の3種類の文字からなる長さNNの文字列が与えられます。この文字列の部分列が(^^)となるものの個数を998244353998244353で割ったあまりを計算してください。

部分列とは文字列中から複数の文字を順序を変えずに取り出して作られる文字列のことです。おなじ文字でも取り出す位置が異なればその文字は異なる文字として扱います。

制約

  • 1N2×1051 \leqq N \leqq 2\times 10^5
  • S=N|S| = N
  • SS()^のみからなる
  • NNは整数

入力

N
S

入力例1

6
(^)^^)

出力例1

3

取り出す位置が、(1,2,4,6)、(1,2,5,6)、(1,4,5,6)の3パターンの部分文字列があります。

入力例2

5
)^^^(

出力例2

0

(^^)が作れない場合もあります。

入力例3

12
(^(^(^^))^))

出力例3

58

Submit


Go (1.21)