Summit Handshakes 2

Time limit2sMemory limit128 MB

Summary

Given N seats around a round table, count the ways N representatives can pair up with non-crossing handshake segments, modulo 987654321.

Level: Medium5 of 10
Topics: Dynamic programming, Combinatorics, Math
Solved: No attempts yet

Problem

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.

Input

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

Output

Print the number of perfect handshake arrangements modulo 987654321.

Examples3

Example 1
Input
```
4
```
Expected output
```
2
```
Example 2
Input
```
2
```
Expected output
```
1
```
Example 3
Input
```
8
```
Expected output
```
14
```