Exactly 2n people are seated evenly around a round table. They all shake hands simultaneously so that everyone is paired with exactly one other person, and no two handshake chords cross inside the circle. Count the number of distinct non-crossing perfect pairings. Two pairings are different if some person shakes a different hand. Report the count modulo 1000000007.
Input format
A single line with one integer n (there are 2n people).
Output format
A single integer: the number of non-crossing perfect pairings, modulo 1000000007.
Constraints
- 0 <= n <= 1000