| UDESC Selection Contest 2023-2 |
|---|
| Закончено |
The fearless explorer Eric is known for his countless adventures and has always been drawn to the unknown. From mysterious forests to towering mountains, he's faced them all. However, in a remote cave, he stumbled upon an object that promised an entirely new challenge: a magic lamp. Upon rubbing the dusty object, to his surprise, a genie emerged. But this was no ordinary genie. He didn't follow the standard rule of granting three wishes to whoever released him.
Instead, the genie was a fan of counting problems and posed a challenge to Eric: he showed Eric a series of opening and closing parentheses, but with a twist: some parentheses were replaced by '?'. With a sly smile, the genie proposed: "Eric, how many ways can you replace the ?'s with '(' or ')' such that the final sequence is balanced? That's the number of wishes you'll have from me."
A sequence of parentheses is considered balanced if it can be transformed into a valid mathematical expression by inserting only digits and operators between the parentheses. In other words, for every opening parenthesis, there must be a corresponding closing parenthesis in the correct order. For instance, "()()" and "(())()" are balanced sequences, but "())(" or "((()()" are not.
Eric needs to calculate how many wishes he has at his disposal by replacing '?' with '(' or ')' such that the resulting sequence is balanced, help him with this task. As this number of wishes can be quite large, print the remainder of the division of this number by $$$10^9+7$$$.
The first line of the input contains an integer $$$N$$$ $$$(1 \le N \le 3000)$$$, the length of the parenthesis sequence.
The second line is the sequence of parentheses with some (possibly none, possibly all) characters turned into '?' by the genie.
Print on a single line the number of wishes Eric can make to the genie modulo $$$10^9+7$$$.
4 ()(?
1
10 ()??(??)??
6
8 ????????
14
6 (?()??
2
| Название |
|---|


