Olympic system#5974

Olympic system

1 second
64 megabytes
Very hard

Two managers are organizing a tournament among teams using the Olympic system. Each team is numbered from to . Due to their busy schedules, the managers only decide which teams will play the next match, always selecting teams with consecutive numbers. All other tasks are managed by their assistants. After each match, the losing team is eliminated, and the remaining teams with higher numbers (if any) are renumbered by decreasing their numbers by . The manager who is available at that moment selects the next pair of teams (both managers cannot be available simultaneously). The tournament concludes when only one team remains. The managers' decisions can be represented by a sequence of numbers, where each number is the smaller team number in the chosen pair.

For example, with teams, if the pairs are chosen in this order: , , , the sequence is . Note that some sequences can define the same pairs of competing teams, differing only in the order of matches. Such sequences are called equivalent.

For instance, the sequence above is equivalent to the sequence . In the first case, teams and compete first, followed by and , and then the winners face each other. In the second case, and compete first, followed by and , and then the winners meet.

Given , determine the maximum number of sequences that can be generated as described above, ensuring no two sequences are equivalent.

Input

The first line contains the number (1 \le N \le 1000000).

Output

Output a single line with the answer to the problem. The answer should be given modulo (10^9+9).

Examples

Example 1

Loading
Loading