(^^)

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

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

• は()^のみからなる
• は整数

N
S

6
(^)^^)

3

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

5
)^^^(

0

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

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

58