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
|