問題一覧 > 通常問題

No.535 自然数の収納方法

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 25
作問者 : PulmnPulmn / テスター : btkbtk
6 ProblemId : 1541 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-06-23 23:28:55

問題文

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

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

・$1\le i\le N$ を満たす全ての$i$において $\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}$ としたときに $A_L-L\lt A_i\lt A_R+R$ が成り立つ。

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

入力

$N$

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

出力

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

サンプル

サンプル1
入力
3
出力
7

条件を満たす自然数の収納方法は$\{1,1,1\},\{1,2,1\},\{2,2,1\},\{2,2,2\},\{2,3,2\},\{3,3,2\},\{3,3,3\}$の7通りです。

サンプル2
入力
5
出力
366

例えば、$\{3,4,5,4,2\}$が条件を満たします。

サンプル3
入力
100
出力
35646100

出力する値は$1{,}000{,}000{,}007$で割ったときの余りであることに注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。