There are N houses in a neighborhood number 1 through N (according to there positions). You are required to make a new big building after removing these houses and you have a machine that destroys the houses. The machine can choose any position for destruction (1 to N−1 in any order). When you select the ith place for the destruction it destroys ith and (i+1)th position houses.
The cost of destruction is equal to the number of positions you choose for destroying the houses.
Now, you select all the positions one after another (in any order) and after finishing this work, you know the order of positions in which the houses are destroyed. After seeing that you made a wrong decision, you know that the total cost of destruction is equal to the number of positions you select before the destruction of the entire neighborhood. The positions that you select after the destruction of the entire neighborhood are not considered in the cost.
Your task is to find the sum of all costs over all possible orders that you know.
Example
There are 4 houses in the neighborhood (1 2 3 4). There are a total of 3! = 6 ways to destroy the whole neighborhood.
(1 3 2): Select position 1 and houses 1 and 2 are destroyed then choose house position 3 it destroys house 3 and 4. All houses are destroyed now, therefore, position 2 is not considered in cost (position 2 is scam did by the driver), the total cost of destruction is 2
(3 1 2): The total cost is 2.
(1 2 3): Select position 1 and destroy houses 1 and 2. Select position 2, it destroys houses 2 and 3 then choose position 3 it destroys houses 3 and 4 all houses are destroyed now. at a cost of 3
(2 3 1): The total cost is 3.
(2 1 3 ): The total cost is 3.
(3 2 1): The total cost is 3.
Therefore, the sum of total cost = 2+2+3+3+3+3 = 16.
Input format
The first line contains N denoting the number of houses in the neighborhood.
Output format
Print the sum of the total cost over all possible ways of destroying the entire neighborhood., modulo 1e9+7.
Constraints
2≤N≤1e6
explained above