3991: 错排问题（staggered）

【题目描述】 创新班有N位同学，编号分别为1,2,3……N，节日到了，陈老师要求每人写一张祝福卡，每张祝福卡上的编号就是写这张卡的同学的编号。现在，陈老师把卡全部收起来再重新分发，希望每位同学都不会拿到自己写的那张卡的话，这就是经典的错排问题。当N=3时，我们可以给1号同学发2号卡，2号同学发3号卡，3号同学发1号卡，当然这只是其中的一种发法。请计算出对于N时，一共有多少种错排的方法？ 【输入格式】 一个整数N，范围是[1,100] 【输出格式】 一个整数。由于这个数可能很大，最后输出这个数 % 100007的结果 【输入样例】 4 【输出样例】 9