0013 - 撹乱順列

Problem

問題文

整数$N$が与えられるので、長さNの撹乱順列の個数$d_N$を$10^9+7$で割った余りを計算してください。 ここで、撹乱順列とは、$1,\ldots,N$の並べ替えであって、すべての$i=1,\ldots,N$に対して、$i$番目が$i$以外であるようなものです。

制約

$0 \le N \le 100000$
100点満点です。
50点分のテストケースは、$N \le 1000$を満たします。

入出力例

入力例 1

4

出力例 1

9
長さ4の撹乱順列の個数は9個です。

入力例 2

0

出力例 2

1
長さ0の唯一の順列(空列)は、撹乱順列です。