Summit Handshakes 2

Country A had been divided into several small states. To reunite it, N representatives from those states have gathered around a round table.

Before the meeting begins, the representatives want to shake hands. Their seats are fixed in advance, each representative must shake hands with exactly one other representative, and all handshakes happen at the same time.

Draw a line segment inside the table for each pair of people shaking hands. If no two such segments cross, then the handshakes are perfect.

Given N, compute the number of ways for all representatives to shake hands perfectly.

The first line contains the number of participants N. N is an even integer not greater than 10,000.

Print the number of perfect handshake arrangements modulo 987654321.