Christmas Party

There are n children at a Christmas party, and each of them has brought a gift. The idea is that everybody will get a gift brought by someone else. In how many ways can the gifts be distributed?

Input

The only input line has an integer n: the number of children.

Output

Print the number of ways modulo 10^9+7.

Constraints

$1 \le n \le 10^6$

Example

Input

4

Output

9