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 \leq i \leq n$, find the largest $j$ such that $1 \leq j < i$ and $p_j > p_i$, and add an undirected edge between node $i$ and node $j$  For every $1 \leq i \leq n$, find the smallest $j$ such that $i < j \leq 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 \le n \le 10^6$).


-----Output-----

Output a single integer $0 \leq 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 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 4$.

Nodes $v_1$, $v_2$, $\ldots$, $v_k$ form a simple cycle if the following conditions hold:   $k \geq 3$.  $v_i \neq v_j$ for any pair of indices $i$ and $j$. ($1 \leq i < j \leq k$)  $v_i$ and $v_{i+1}$ share an edge for all $i$ ($1 \leq i < k$), and $v_1$ and $v_k$ share an edge.

Difficulty: interview

Starter code:

Solutions:
MOD = 10 ** 9 + 7

out = 1

n = int(input())

for i in range(n):
    out *= (i + 1)
    out %= MOD
out -= pow(2, n - 1, MOD)
print(out % MOD)


n=int(input())
ans=1
mod=10**9+7
for i in range(2,n+1):ans=ans*i%mod
print((ans-2**(n-1))%mod)

import sys
import random
from math import *
 
def input():
    return sys.stdin.readline().strip()
 
def iinput():
    return int(input())

def finput():
    return float(input())

def tinput():
    return input().split()

def linput():
    return list(input())
 
def rinput():
    return map(int, tinput())

def fiinput():
    return map(float, tinput())
 
def rlinput():
    return list(map(int, input().split()))
def trinput():
    return tuple(rinput())

def srlinput():
    return sorted(list(map(int, input().split())))

def NOYES(fl):
    if fl:
        print("NO")
    else:
        print("YES")
def YESNO(fl):
    if fl:
        print("YES")
    else:
        print("NO")
    
def main():  
    n = iinput()
    res, ans, mod = 1, 1, int(1e9 + 7)
    for i in range(1, n + 1):
        res = res * i % mod
    for i in range(1, n):
        ans = ans * 2 % mod
    print((res - ans + mod) % mod)
    
            
    
    

    
for inytd in range(1):
    main()

from collections import *
from sys import stdin,stderr
def rl():
    return [int(w) for w in stdin.readline().split()]

MOD = 1000000007

n, = rl()
r = 0
i1f = 1
for i in range(2, n + 1):
    r = (2 * r + i1f * (i - 2)) % MOD
    i1f = i1f * i % MOD
print(r)


n = int(input())
MOD = 10 ** 9 + 7
ans1 = 1
ans2 = 1
for i in range(1,n+1):
    ans1 *= i
    ans1 %= MOD
for i in range(n-1):
    ans2 *= 2
    ans2 %= MOD
print((ans1 - ans2) % MOD)

from sys import stdin
input = stdin.readline

n = int(input())
res1, res2 = 1, 0
mod = 1000000007

for x in range(2, n + 1):
    res1 = (res1 * x) % mod

res2 = pow(2, n - 1, mod)

print((res1 - res2) % mod)

#import sys
#input = sys.stdin.readline
Q = 10**9+7
def main():
    n = int( input())
    ans = 1
    for i in range(1,n+1):
        ans *= i
        ans %= Q
    ans = (ans - pow(2, n-1,Q))%Q
    print(ans)
def __starting_point():
    main()

__starting_point()

import sys
input = sys.stdin.readline

N = int(input())

MOD = 10**9 + 7

start = 1
to_remove = 1
for i in range(1, N+1):
    start = (start * i) % MOD
    if i > 1:
        to_remove = (to_remove * 2) % MOD
    # print(start, to_remove)
res = (start - to_remove) % MOD
print(res)


def main():
    n = int(input())
    mod = 10**9+7
    f = 1
    for i in range(1,n+1):
        f *= i
        f %= mod

    f -= pow(2,n-1,mod)
    f %= mod
    print(f)

main()