Problem Statement

MAK loves natural numbers.

MAK has at least $N$ copies of each natural number from $1$ to $N$. He decided to store some of the natural numbers he owns in boxes. Conveniently, $N$ mutually distinguishable boxes are lined up in a row in front of him. He plans to store $1$ of the natural numbers he owns in each box, but the following condition must be satisfied. Here, let $A_i$ denote the natural number stored in the $i$-th box from the left.

・For every $i$ satisfying $1\le i\le N$, letting　$\begin{eqnarray}L=\begin{cases}N&(i=1)\\i-1&(i\neq 1) \end{cases}\end{eqnarray}$　　$\begin{eqnarray}R=\begin{cases}i+1&(i\neq N)\\1&(i=N) \end{cases}\end{eqnarray}$　, it holds that $A_L-L\lt A_i\lt A_R+R$.

MAK wondered how many ways there are to store the natural numbers so that the above condition is satisfied. Since this value can be very large, output the remainder when it is divided by $1{,}000{,}000{,}007=10^9+7$.

Input

$N$

$3\le N\le 2{,}000$

Output

Output the remainder when the number of ways to store the numbers satisfying the condition is divided by $1{,}000{,}000{,}007$. Print a newline at the end.

Sample

3

7

5

366

100

35646100