Penguin Navigator

Time limit1sMemory limit1024 MB

Summary

Count the numberings of a 2 by N grid with 1 to 2N such that every right or down move from (1,1) to (2,N) increases the tile number.

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

Problem

A penguin is at $(1, 1)$ . The penguin wants to get home. Its home is at $(2, N)$ . However, someone broke all the ice paths, so it can no longer get home. Hyeonjin will build ice paths for the penguins. The ice path is $2 \times N$ in size, and each ice tile can be numbered from $1$ to $2N$ with no repeats. These penguins have a peculiar habit. A penguin moves only right or down from its current position. However, the number of the tile it moves to must be greater than the number of the tile it came from. Write a program to find the number of ice paths that let a penguin reach home no matter how it moves.

Input

The first line gives the horizontal length $N$ of the ice path ( $1 \leq N \leq 10\,000$ ).

Output

On the first line, print the number of ice paths modulo $10^9+7$ .

Examples1

Example 1
Input
```
3
```
Expected output
```
5
```