P13004

错排问题

难度 3 级 小学 算法入门 递推
讨论 统计 17通过 33提交 51.5%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

有 n 个不同的元素和 n 个不同的位置,每个元素都有一个原本属于自己的位置(即第 i 个元素对应第 i 个位置)。现在要求将这 n 个元素重新排列,使得没有任何一个元素放在它原本的位置上。这种排列称为错排(Derangement)。

请计算所有可能的错排方案数,并对 10^9 + 7 取模。

输入

输入只有一行,包含一个整数 n ( 1 \le n \le 2000 )。

输出

输出一个整数,表示错排方案数对 10^9 + 7 取模后的结果。

样例

样例 1
输入
2
输出
1
样例 2
输入
200
输出
96428448
Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交