Little W is a master of randomness and is particularly fond of randomized algorithms.

One day, Little W starts his random walk from the origin $(0,0)$.

In each step, Little W chooses a vector $(x,y)$ uniformly at random such that $x,y \in \mathbb R$ and $|x|+|y|\le 1$. He then moves along this vector exactly once; that is, if his current coordinate is $(A, B)$, Little W moves to $(A+x, B+y)$.

Little W performs a total of $n$ such walk operations. After completing all $n$ operations, Little W ends his walk.

Little W is interested in the result of the walk and wants to know the expected distance from his final position to the $y$-axis. That is, if the final coordinate is $(A, B)$, you need to find the expected value of $|A|$.

Since the expression for the answer may be very complex, you only need to output the result modulo the prime $p=1\,000\,000\,007$ $(10^9+7)$.

Input

A single positive integer $n$, representing the number of operations performed by Little W.

Output

A single positive integer representing the answer modulo the prime $p=1\,000\,000\,007$ $(10^9+7)$.

It can be proven that for all inputs, the answer can always be expressed in the form $\frac xy$ $(y \not\equiv 0 \pmod p)$, in which case you only need to output the result of $(x\times y^{p-2})\bmod p$.

Examples

Input 1

1

Output 1

333333336

Note 1

For Example 1, the answer is equal to $\displaystyle\int_0^1 x^2\,\mathrm dx=\frac13$.

Input 2

3

Output 2

769047625

Note 2

For Example 2, the answer is equal to $\frac{239}{420}$.

Constraints

Test set 1 ($5\%$): $n \le 3$;

Test set 2 ($10\%$): $n \le 10$;

Test set 3 ($10\%$): $n \le 30$;

Test set 4 ($15\%$): $n \le 200$;

Test set 5 ($15\%$): $n \le 2000$;

Test set 6 ($15\%$): $n \le 2\times 10^5$;

Test set 7 ($30\%$): $n \le 5\times 10^6$.