U588121 错位排列？

题目描述

给定一个正整数 $n$，表示序列 $a_n$ 的长度为 $n$，现在需要你对这个序列 $a_n$ 进行排列，若它满足：

• $a_i\ne i$
• $a_{a_{a_i}}\ne i$

以上两个条件，我们就认为它是合法的，现在，给定一个正整数 $N$，当 $n=N$ 时，序列 $a_n$ 的合法排列有多少种？注意，最后答案可能很大，故需要将答案 $\bmod 10^7+7$ 后再输出。

输入格式

一个正整数 $N$。

输出格式

一行，一个正整数 $M$ 表示答案 $\bmod 10^7+7$ 后的结果。

输入输出样例 #1

输入 #1

9

输出 #1

52552

输入输出样例 #2

输入 #2

1

输出 #2

0

说明/提示

数据范围

对于正整数 $N$，保证满足 $1\le N \le 1000$。

声明：无法保障数据的正确性，如果数据有错也请各位dalao指出。

原题(数据在附件中)