Your task is to calculate the number of valid bracket sequences of length $n$ when a prefix of the sequence is given.
The first input line has an integer $n$ .
The second line has a string of $k$ characters: the prefix of the sequence.
Print the number of sequences modulo $10^9+7$ .
6 (()\n \n
2\n
There are two possible sequences: (())() and (()()) .