human
Can you provide a Python program to 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 given the following:
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. 
Using python3 can you solve the prior task?
assistant
#Here is Python program to 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 
.

import io
import os

from collections import Counter, defaultdict, deque


def findCycle(source, getNbr):  # via bfs for a undirected graph
    q = deque([source])
    dist = {source: 0}
    parent = {source: None}
    while q:
        node = q.popleft()
        d = dist[node]
        for nbr in getNbr(node):
            if nbr not in dist:
                q.append(nbr)
                dist[nbr] = d + 1
                parent[nbr] = node
            else:
                # If nbr is already assigned a dist, it can only one of [d-1, d, d+1]
                if dist[nbr] == d - 1:
                    assert nbr == parent[node]  # Ignore 2-cycles
                    continue
                assert dist[nbr] in [d, d + 1]
                # Follow backpointers until hit LCA of nbr and node to form cycle
                path1 = [nbr]
                path2 = [node]
                while path1[-1] != path2[-1]:
                    if dist[path1[-1]] >= dist[path2[-1]]:
                        path1.append(parent[path1[-1]])
                    else:
                        path2.append(parent[path2[-1]])
                assert path1[-1] == path2[-1]
                path2.pop()
                return path1 + path2[::-1]

    return None

def solveBrute(N, ):
    MOD = 10 ** 9 + 7

    from itertools import permutations
    count = 0
    for perm in permutations(range(N)):

        def getNbr(i):
            ret = []
            for j in reversed(range(i)):
                if perm[j] > perm[i]:
                    ret.append(j)
                    break

            for j in range(i + 1, N):
                if perm[j] > perm[i]:
                    ret.append(j)
                    break
            return ret
        works = False
        for i in reversed(range(N)):
            
            works = findCycle(i, getNbr)
            if works:
                break
        if works:
            #print(perm, works)
            count += 1

    return count

def solve(N, ):
    MOD = 10 ** 9 + 7
    fact = [1]
    for i...