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.util.*;
import java.io.*;
import java.lang.*;


public class graph {
    static long mod=10000_00007;
    public static long binexp(long a,long b){
        long res=1;
        while(b>0){
            if((b&1)==1){
                res=res*a;  res=res%mod;
            }
            a=a*a; a=a%mod;
            b>>=1;
        }
        return res;
    }
    public static void main(String[] args) throws Exception{
        InputStreamReader ip=new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(ip);
		int n = Integer.parseInt(br.readLine());
        // StringBuilder sb = new StringBuilder();
        
        long fact=1;
        for(int i=1;i<=n;i++){
            fact=((long)(fact*(long)(i)));
            fact=fact%mod;
        }

        long ump=binexp(2, n-1);//(long)(Math.pow(2, n-1));
        ump=ump%mod;
        long ans=fact-ump;
        if(ans<0){ans+=mod;}
        System.out.println(ans);
    }
}



    // public static void main(String[] args) throws Exception{
    //     InputStreamReader ip=new InputStreamReader(System.in);
    //     BufferedReader br = new BufferedReader(ip);
	// 	// int t = Integer.parseInt(br.readLine());
	// 	StringBuilder sb = new StringBuilder();
 
	// 	// while (t-- > 0) {
	// 		String[] arrp = (br.readLine()).trim().split(" ");
           
    //         int n = Integer.parseInt(arrp[0]);
    //         int m= Integer.parseInt(arrp[1]);
            
    //         boolean[] invalid=new boolean[n+1];
    //         for(int i=0;i<m;i++){
    //             String[] pr = (br.readLine()).trim().split(" ");
    //             int val=Integer.parseInt(pr[0]);
    //             invalid[val]=true;
    //             val=Integer.parseInt(pr[1]);
    //             invalid[val]=true;
    //         }
    //         int valid=-1;
    //         for(int i=1;i<=n;i++){
    //             if(!invalid[i]){valid=i; break;}
    //         }            

    //         System.out.println(n-1);
    //         for(int i=1;i<=n;i++){
    //             if(i!=valid){System.out.println(valid+" "+i);}
    //         }
    //     }
    // }



  //Q1  
//     static int mcost=0;
//     public static void dfs(ArrayList<ArrayList<Integer>> graph,int s,boolean[] visited,int[] cost){
//         mcost=Math.min(mcost,cost[s-1]);
//         visited[s]=true;
//         for(int nbr:graph.get(s)){
//             if(visited[nbr]==false){
//                 dfs(graph,nbr,visited,cost);
//             }
//         }
//     }
//     public static void main(String[] args) throws Exception{
//         InputStreamReader ip=new InputStreamReader(System.in);
//         BufferedReader br = new BufferedReader(ip);
// 		// int t = Integer.parseInt(br.readLine());
// 		StringBuilder sb = new StringBuilder();
 
// 		// while (t-- > 0) {
// 			String[] arrp = (br.readLine()).trim().split(" ");
           
//             int n = Integer.parseInt(arrp[0]);
//             int m= Integer.parseInt(arrp[1]);
            
//             String[] strs = (br.readLine()).trim().split(" ");
//             int[] cost=new int[n];
//             ArrayList<ArrayList<Integer>> graph=new ArrayList<>();
//             graph.add(new ArrayList<>());
//             for(int i=0;i<n;i++){
//                 cost[i]=Integer.parseInt(strs[i]);
//                 graph.add(new ArrayList<>());
//             }

            
//             for(int i=0;i<m;i++){
//                 arrp = (br.readLine()).trim().split(" ");
//                 int u = Integer.parseInt(arrp[0]);
//                 int v= Integer.parseInt(arrp[1]);

//                 (graph.get(u)).add(v);
//                 (graph.get(v)).add(u);
//             }

//             //dfs
//             boolean[] visited=new boolean[n+1];
//             long ans=0;
//             for(int i=1;i<=n;i++){
//                 if(visited[i]==false){
//                     mcost=Integer.MAX_VALUE;
//                     dfs(graph,i,visited,cost);
//                     ans+=mcost;
//                 }
//             }

//             System.out.println(ans);
//         // }
//     }
// }
