(^^)

問題

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

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

制約

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

入力

N
S

入力例１

6
(^)^^)

出力例１

3

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

入力例２

5
)^^^(

出力例２

0

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

入力例３

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

出力例３

58