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?
The only input line has an integer $n$ : the number of children.
Print the number of ways modulo $10^9+7$ .