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. 
from collections import deque
from collections import OrderedDict
import math
 
import sys
import os
import threading
import bisect
 
import operator
 
import heapq
 
 
from atexit import register
from io import BytesIO
 
#sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
#sys.stdout = BytesIO()
#register(lambda: os.write(1, sys.stdout.getvalue()))
 
 
import io
#input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
#sys.stdin = open("F:\PY\\test.txt", "r")
input = lambda: sys.stdin.readline().rstrip("\r\n")
#input = sys.stdin.readline

#a = [int(x) for x in input().split()]



mod = 1000000007

n = int(input())
factor = 1
for i in range(2, n+1):
    factor=(factor*i)%mod

power2 = 1
for i in range(1, n):
    power2=(power2*2)%mod
answer = factor-power2
if answer<0:
    answer+=mod
print(answer)
    










'''
for _ in range(int(input())):
    
    n = int(input())
    ar = list(map(int, input().split()))
    dp = [0]*100005
    for i in range(n):
        dp[ar[i]]+=1
    ar.clear()
    for i in range(len(dp)):
        if dp[i]!=0:
            ar.append(dp[i])       
    ar.sort()
    maxC = ar[len(ar)-1]
    sumA = sum(ar)
    answer=0
    for i in range(len(ar)):
        if ar[i]==maxC:
            answer+=1
            sumA-=maxC
    answer-=1
    answer+= min(sumA//(maxC-1), len(ar)-1)
    print(answer)
    #sys.exit(0)   
         
    




def maxDisjointIntervals(list_):
    list_.sort(key=lambda x: x[1])
    print(list_[0][0], list_[0][1])
    r1 = list_[0][1]
    for i in range(1, len(list_)):
        l1 = list_[i][0]
        r2 = list_[i][1]
        if l1>r1:
            print(l1, r2)
            r1 = r2

if __name__ =="__main__1":
    N=4
    intervals = [[1, 4], [2, 3], [4,6], [8,9]]
    maxDisjointIntervals(intervals)
    
    '''
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    