题目描述

尼古拉·伯努利给欧拉写了 $n$ 封信件，对应 $n$ 个信封，然而粗心的秘书却把所有信件都装错了信封，那么一共有多少种装错的装法？

由于答案可能很大，你只需要输出答案 mod $(10^9 + 7)$ 的结果。

输入

一个整数 $n$

输出

装错的方案总数 mod (10^9 + 7) 的结果

样例输入

3

样例输出

2

样例解释

假设信件为 1、2、3，信封为 A、B、C

正确的装法应该为：1->A, 2->B, 3->C

全部装错的方案有 2 种：

1->B, 2->C, 3->A

1->C, 2->A, 3->B

数据范围

$1 ≤ n ≤ 10^7$