I. topoLogical problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

fractal loves geometry, so let's place him in a space he's familiar with, a two-dimensional plane. Initially, fractal is at coordinate O(0, 0) and facing the Ox axis. He was given a task, a piece of paper, and an even number $$$n$$$ $$$(4 \le n \le 10^6)$$$, the reason and purpose of which few know, but such is fate. He needs to perform exactly n operations, each operation happens as follows:

  • fractal chooses any positive integer X.
  • Gradually move X cells directly forward in the direction he is currently facing.
  • Turn either right or left and write down the chosen turn on the paper.

If after performing all operations, fractal ends up at coordinate O(0, 0) and facing the Ox axis, and also never, except for the very last moment of the last operation, was at a coordinate he visited before, then the resulting record on the paper will be called the «answer» to the task.

But since fractal loves to count everything and Catalan numbers, he wanted to count how many «answers» he could get. Since the answer can be very large, output it modulo $$$10^9 + 7$$$.

Input

The first line contains a single even number $$$n$$$ $$$(4 \le n \le 10^6)$$$.

Output

Output a single number, the number of «answers» modulo $$$10^9 + 7$$$.

Examples
Input
4
Output
2
Input
6
Output
12
Note

Note that after a series of operations:

  • X = 4, R — coordinate (0, 4)
  • X = 2, R — coordinate (2, 4)
  • X = 2, R — coordinate (2, 2)
  • X = 4, L — coordinate (-2, 2)
  • X = 2, L — coordinate (-2, 0)
  • X = 2, L — coordinate (0, 0)
The resulting record on paper will not be considered an answer, as the cell $$$(0, 2)$$$ was visited twice.