No.336 門松列列
nmnmnmnmnmnmnm問題文最終更新日: 2016-05-24 14:44:17
問題文
門松列とは3つの整数が左からA、B、Cと並んでいる時に、
全ての値が異なりA、B、Cのうち2番目に大きな整数がAかCである場合をいう。
今回の問題ではある個数の整数が左から横に1列に並んでいるときに、
どの連続した3つの整数を取り出しても門松列になっているものを門松列列と呼ぶ。
1からNまでの正の整数の並べ替えを順列ですべて行うとき、
門松列列になっているものはいくつあるか？
答えは1000000007で割った余りを答えとする。
※N=1、N=2のとき3つの整数を取り出せ無いので答えは0通りとします。
入力
N
問題文中の正の整数N。$1\le N \le 2016$。
出力
問題の答えを1000000007で割った余りを1行で出力せよ。
ただし、最後に改行を忘れずに。
サンプル
サンプル1
入力
1
出力
0
N=1のときに門松列はできませんので答えは0です。
N=2のときも答えは0ですね。
サンプル2
入力
3
出力
4
Nが3のときに順列となるものは、
{1,2,3}、{1,3,2}、{2,1,3}、{2,3,1}、{3,1,2}、{3,2,1}の6つである。
このうち門松列列と呼べるものは、
{1,3,2}、{2,1,3}、{2,3,1}、{3,1,2}の4つである。
サンプル3
入力
4
出力
10
門松列列は、
{1,3,2,4}、{1,4,2,3}、{2,1,4,3}、{2,3,1,4}、{2,4,1,3}、
{3,1,4,2}、{3,2,4,1}、{3,4,1,2}、{4,1,3,2}、{4,2,3,1}
の10個あります。
サンプル4
入力
2016
出力
254936125
最大ケースです。1000000007で割るのを忘れずに。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。