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

import java.io.*;
import java.math.BigDecimal;
import java.math.MathContext;
import java.util.*;


/*
 * @author: Ramanqul
 * */
public class Main {
    private static boolean USE_TEST_CASES = false;
    private static final double EPS = .000000001;

    private static class Graph
    {
        private int V;   // No. of vertices
        private LinkedList<Integer> adj[]; // Adjacency List Represntation

        // Constructor
        Graph(int v) {
            V = v;
            adj = new LinkedList[v];
            for(int i=0; i<v; ++i)
                adj[i] = new LinkedList();
        }

        // Function to add an edge into the graph
        void addEdge(int v,int w) {
            adj[v].add(w);
            adj[w].add(v);
        }

        // A recursive function that uses visited[] and parent to detect
        // cycle in subgraph reachable from vertex v.
        Boolean isCyclicUtil(int v, Boolean visited[], int parent)
        {
            // Mark the current node as visited
            visited[v] = true;
            Integer i;

            // Recur for all the vertices adjacent to this vertex
            Iterator<Integer> it = adj[v].iterator();
            while (it.hasNext())
            {
                i = it.next();

                // If an adjacent is not visited, then recur for that
                // adjacent
                if (!visited[i])
                {
                    if (isCyclicUtil(i, visited, v))
                        return true;
                }

                // If an adjacent is visited and not parent of current
                // vertex, then there is a cycle.
                else if (i != parent)
                    return true;
            }
            return false;
        }

        // Returns true if the graph contains a cycle, else false.
        Boolean isCyclic()
        {
            // Mark all the vertices as not visited and not part of
            // recursion stack
            Boolean visited[] = new Boolean[V];
            for (int i = 0; i < V; i++)
                visited[i] = false;

            // Call the recursive helper function to detect cycle in
            // different DFS trees
            for (int u = 0; u < V; u++)
                if (!visited[u]) // Don't recur for u if already visited
                    if (isCyclicUtil(u, visited, -1))
                        return true;

            return false;
        }


        // Driver method to test above methods
        public static void main2(String args[])
        {
            // Create a graph given in the above diagram
            Graph g1 = new Graph(5);
            g1.addEdge(1, 0);
            g1.addEdge(0, 2);
            g1.addEdge(2, 1);
            g1.addEdge(0, 3);
            g1.addEdge(3, 4);
            if (g1.isCyclic())
                System.out.println("Graph contains cycle");
            else
                System.out.println("Graph doesn't contains cycle");

            Graph g2 = new Graph(3);
            g2.addEdge(0, 1);
            g2.addEdge(1, 2);
            if (g2.isCyclic())
                System.out.println("Graph contains cycle");
            else
                System.out.println("Graph doesn't contains cycle");
        }
    }


    private static boolean isCyclic(int a[]) {
        int n = a.length;
        Graph graph = new Graph(n);

        for (int i=0;i<n;i++) {
            for (int j=0;j<i;j++) {
                if (a[i] < a[j]) {
                    graph.addEdge(i, j);
                    break;
                }
            }

            for (int j=i+1;j<n;j++) {
                if (a[i] < a[j]) {
                    graph.addEdge(i, j);
                    break;
                }
            }
        }

        return graph.isCyclic();
    }

    private static void printArr(int a[], int n) {
        for (int i=0; i<n; i++) {
            System.out.print(a[i] + " ");
        }

        System.out.println();
    }

    private static int perm(int a[], int size, int n) {
        int ans = 0;
        if (size == 1) {
            if (isCyclic(a)) {
                System.out.print("*");
                ans++;
            }

            printArr(a, n);
        }

        for (int i=0; i<size; i++) {
            ans += perm(a, size-1, n);

            if (size % 2 == 1) {
                int temp = a[0];
                a[0] = a[size-1];
                a[size-1] = temp;
            } else {
                int temp = a[i];
                a[i] = a[size-1];
                a[size-1] = temp;
            }
        }

        return ans;
    }


    private static void solve(final int testCase, MyScanner in, PrintWriter out) {
        int n = in.nextInt();

        /*
        int a[] = new int[n];
        for (int i=1;i<=n;i++) {
            a[i-1]=i;
        }

        int ans = perm(a, a.length, n);
        */

        int MOD = 1_000_000_007;

        long x = 1;
        //n!-2^(n-1)
        for (int i=1;i<=n;i++) {
            x = ((x % MOD) * (i%MOD))%MOD;
        }

        long y = 1;
        for (int i=1;i<n;i++) {
            y = ((y % MOD) * 2)%MOD;
        }

        long ans = (x % MOD - y % MOD) % MOD;

        out.println(ans);
    }



    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        int t = 1;

        if (USE_TEST_CASES) {
            t = sc.nextInt();
        }

        for (int i=0;i<t;i++) {
            solve(i, sc, out);
        }
        out.close();
    }

    private static class Pair<A,B> {
        public A first;
        public B second;
        public Pair(A first, B second) {
            this.first = first;
            this.second = second;
        }
    }

    private static class Triple<A,B,C> {
        public A first;
        public B second;
        public C third;

        public Triple(A first, B second, C third) {
            this.first = first;
            this.second = second;
            this.third = third;
        }
    }

    private static class H {
        public static void readArray(MyScanner in, int a[], int n) {
            for (int i=0;i<n;i++) {
                a[i] = in.nextInt();
            }
        }

        public static boolean isUnique(int ... nums) {
            Set<Integer> s = new HashSet<>();
            for (int i:nums) {
                if (s.contains(i)) {
                    return false;
                }
                s.add(i);
            }

            return true;
        }


        public static Pair<Integer, Integer>[] readIntPairs(MyScanner in, int n) {
            Pair[] pairs = new Pair[n];
            for (int i=0;i<n;i++) {
                int x = in.nextInt();
                int y = in.nextInt();
                pairs[i] = new Pair<Integer, Integer>(x, y);
            }

            return pairs;
        }

        public static List<Integer> dfs(int start, List<Integer>[] adj) {
            boolean v[] = new boolean[adj.length+1];

            List<Integer> res = new ArrayList<>();

            Stack<Integer> st = new Stack<>();

            st.push(start);

            while (!st.isEmpty()) {
                int x = st.pop();
                if (!v[x]) {
                    res.add(x);
                    boolean allVisited = true;
                    for (int e: adj[x]) {
                        if (!v[e]) {
                            st.push(e);
                            allVisited = false;
                        }
                    }

                    if (allVisited) {
                        break;
                    }

                    v[x] = true;
                } else {
                    break;
                }
            }

            return res;
        }

        public static long gcd(long a, long b) {
            if (a == 0) {
                return b;
            }

            return gcd(b%a, a);
        }

        public static long lcm(long a, long b) {
            return (a * b) / gcd(a,b);
        }
    }

    private static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        public MyScanner(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine(){
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

    }
}