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.