Mahmoud together with his friends visited Georgia. They would stay in a hotel at Rustavelli. When the cowboys reached the hotel, they hung their hats in the entrance and settled in. The beer bottles on the table could not escape from Mahmoud's attention when passing through the corridor. At the suggestion of Mahmoud, all the cowboys began drinking. They drank too much, thus none of them was mindful. Then they decided going downtown. On the way out, everyone had a hat on, but they mixed up the hats as they were so drunk.

The man who is able to have on his own hat while he is drunk is considered clever and who is not able to do so is considered stupid.

You are given the number of cowboys - n (including Mahmoud). You should find in how many ways the cowboys may have on the hats so that all of them are stupid. Two ways are considered different if there is at least one cowboy who has a hat in this case and another hat in the other case.

As the answer may become very large, you should output the result modulo 109 + 7.

Input

Given the number of cowboys - n (1 ≤ n ≤ 107).

Output

The answer to the problem as specified above.