問題文

MAK君は自然数が大好きです。

MAK君は$1$から$N$の自然数を、それぞれ$N$個以上持っています。MAK君は自分が持っている自然数のいくつかを箱の中に収納しようと思いました。都合の良いことに、MAK君の目の前に互いに区別できる$N$個の箱が横一列に並んでいます。MAK君はそれぞれの箱に、自分が持っている自然数の中から$1$つを収納しようと計画していますが、以下の条件を満たす必要があります。ただし、左から$i$番目の箱に収納される自然数を$A_i$とあらわすことにします。

・$1\le i\le N$ を満たす全ての$i$において　$\begin{array}{r}L=\{\begin{array}{ll}N& (i=1)\\ i-1& (i\ne 1)\end{array}\end{array}$　　$\begin{array}{r}R=\{\begin{array}{ll}i+1& (i\ne N)\\ 1& (i=N)\end{array}\end{array}$　としたときに $A_L-L<A_i<A_R+R$ が成り立つ。

MAK君は上の条件を満たす自然数の収納方法は何通りあるのか気になりました。この値は非常に大きくなる場合があるので、$\mathrm{1,000,000,007}={10}^9+7$ で割ったときの余りを出力してください。

入力

$N$

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

出力

条件を満たす収納方法の通り数を $\mathrm{1,000,000,007}$ で割ったときの余りを出力してください。最後に改行してください。

サンプル

3

7

5

366

100

35646100