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.
A single line with one integer n (there are 2n people).
A single integer: the number of non-crossing perfect pairings, modulo 1000000007.
Example 1
Input
3
Expected
5
Explanation
With 6 people there are 5 non-crossing perfect pairings (the 3rd Catalan number).
Example 2
Input
0
Expected
1
Explanation
With nobody at the table there is exactly one (empty) pairing, so the answer is 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →