PermutatioNS#12854

PermutatioNS

1 second
256 megabytes
Hard

For a permutation of the numbers from to , define as follows: for every pair with 1 \le i \le j \le n, consider the pair , where is the smallest of the numbers p_i, p_{i+1}, \ldots, p_j and is the largest of them. Then equals the number of distinct pairs among all \frac{n(n+1)}{2} pairs.

For example, consider the permutation (1, 3, 2).

There are distinct pairs in total, so f((1, 3, 2)) = 5.

Find the sum of over all permutations of length , modulo 10^9 + 7.

Input

The only line contains one integer (1 \le n \le 2\cdot 10^5).

Output

Print the sum of over all permutations of length , modulo 10^9 + 7.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Example 4

Loading
Loading