There was an issue with the judge solution of problem H  Bracket Sequence. All solutions have been rejudged.
Given an integer $n$, find the number of balanced bracket sequences of length $n$, that have the sequence "((())" as a subarray.
A sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters '+' and '1'. For example, sequences "(())()", "()", and "(()(()))" are balanced, while ")(", "(()", and "(()))(" are not.
Print the answer $(mod$ $10^9 + 7)$.
The input is made up of one line containing an integer $n$ $(1 \leq n \leq 1000)$.
Print a single integer the answer to the problem.
Input  Output 

6 Copy

1 Copy

8 Copy

4 Copy
