#P1017. 错排问题

错排问题

当前没有测试数据。

题目描述

小C好久没有跟小Q联系了,他想把自己最近的一些情况告诉小Q。他把想说的事情,分成n类,他把每类的名称都写在信封上,比如学习、工作、生活。有了分类之后,接下来就是写内容了,这花了小C好长的时间。写完每种分类的内容之后,就是把信装进信封里了。这个时候,小C想,有多少种情况把所有的信都装错了,即每封信的标题和内容都对不上。请你帮他算算。

格式

输入格式

输入一个整数n,表示分类的个数。答案比较大,对1000710007取余。

输出格式

输出全部都装错了的方案数。

样例数据

3
2

样例解释

当n=3 时,有下列两种情况是完全装错了。

3 1 2
2 3 1

数据规模与约定

对100%的数据,n的范围[1,100]。