A permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).

Consider a permutation p of length n, we build a graph of size n using it as follows: 

  * For every 1 ≤ i ≤ n, find the largest j such that 1 ≤ j < i and p_j > p_i, and add an undirected edge between node i and node j 
  * For every 1 ≤ i ≤ n, find the smallest j such that i < j ≤ n and p_j > p_i, and add an undirected edge between node i and node j 



In cases where no such j exists, we make no edges. Also, note that we make edges between the corresponding indices, not the values at those indices.

For clarity, consider as an example n = 4, and p = [3,1,4,2]; here, the edges of the graph are (1,3),(2,1),(2,3),(4,3).

A permutation p is cyclic if the graph built using p has at least one simple cycle. 

Given n, find the number of cyclic permutations of length n. Since the number may be very large, output it modulo 10^9+7.

Please refer to the Notes section for the formal definition of a simple cycle

Input

The first and only line contains a single integer n (3 ≤ n ≤ 10^6).

Output

Output a single integer 0 ≤ x < 10^9+7, the number of cyclic permutations of length n modulo 10^9+7.

Examples

Input


4


Output


16

Input


583291


Output


135712853

Note

There are 16 cyclic permutations for n = 4. [4,2,1,3] is one such permutation, having a cycle of length four: 4 → 3 → 2 → 1 → 4.

Nodes v_1, v_2, …, v_k form a simple cycle if the following conditions hold: 

  * k ≥ 3. 
  * v_i ≠ v_j for any pair of indices i and j. (1 ≤ i < j ≤ k) 
  * v_i and v_{i+1} share an edge for all i (1 ≤ i < k), and v_1 and v_k share an edge. 
66
 652615
 482331
 336161
 33
 1000000
 79531
 768208
 3
 885131

257415584
 960319213
 722928541
 234634596
 762187807
 23581336
 162141608
 635322133
 2
 329995454

"""
Cyclic Permutation

The answer is n! − 2^(n−1)

.

Consider an arbitrary cyclic permutation — for example, [4,2,3,1,5,6]; it contains many cycles of length 3
: [1,2,3], [1,3,5], [3,4,5]. Note that all the listed cycles contain nodes obtained from just one choice of i. We can generalize this to the following. If for any i, we make edges on both sides of it, this will create a simple cycle of length 3

. The proof is simple and is an exercise for you.

Thus, there has to at most one peak that is the element n
– all acyclic permutations increase, then reach n, and, finally, decrease. These are formally called unimodal permutations, and it's easy to see that any unimodal permutation forms a tree, and, thus, contains no simple cycle  — each element, except n

, has a uniquely defined parent.

We can construct any unimodal permutation by adding the numbers n,n−1,…,1
into a deque in the same order. For example, [2,3,4,1] can be constructed by first pushing 4, 3, 2 to the front, and, finally, 1 at the back. Thus, for every element, except n, we have the choice of pushing it to the front or the back, making the total number of ways equal to 2^(n−1)

.

Time Complexity: O(n)
"""

import sys
read = lambda: sys.stdin.readline().strip()

n = int(read())
MOD = 1e9 + 7
fact = 1
two_pow = 1
for i in range(2, n+1):
    fact = (i * fact) % MOD
    two_pow = (2 * two_pow) % MOD

print(int(int(fact - two_pow) % MOD))