people guests sitting around a round table, and their number is even. The guests split into pairs, and each pair shakes hands across the table, so people / 2 handshakes happen at once.
Think of every handshake as a chord of the circle. In how many ways can the guests be paired so that no two chords cross?
The answer can be huge, so return it modulo 10^9 + 7.people=2 → 1
Two guests can only shake hands with each other, so there is one way.
people=6 → 5
Guest 1 can shake hands with guest 2, 4 or 6 (not 3 or 5: that would leave a single guest stranded on one side). That gives 2 + 1 + 2 = 5 ways.
people=10 → 42
people is evenpeople=2
1
Run checks the first 3 tests in your browser. Submit checks all 40 tests on the server, hidden ones included.