Curse of the Meeting
Time limit1sMemory limit256 MB
Count the ways N people around a round table can pair up and shake hands simultaneously without any arms crossing, modulo 987654321.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Combinatorics, Math, Recursion
- Solved
- No attempts yet
Problem
Isani, a student in the Computer Science and Engineering department at Inha University, is going to a meeting for the first time in a while. The meeting has N people sitting around a round table. Isani's jealous friend Myeonggi cast the curse of X. The curse makes the meeting fail if, when the N people all pair up into two-person groups and shake hands at the same time, any arms cross or even one person cannot shake hands. Myeonggi gave Isani a chance to lift the curse. If Isani works out the number of ways the meeting can succeed and shouts it out loud, the curse is lifted. Isani lacks the computational skill, so he asks for your help. Write a program that lifts the curse on Isani.
When 4 people attend the meeting, there are 2 ways for the meeting to succeed, as in the figure below.
When 6 people attend the meeting, there are 5 ways for the meeting to succeed, as in the figure below.
Input
The first line gives the number of people attending the meeting, N. This value is an even number less than or equal to 10,000.
Output
Print the number of ways the meeting can succeed modulo 987654321.