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

//package codeforces;
import java.io.PrintWriter;
import java.util.*;
public class solution { 
	static long MOD=1000000007;
    public static void main(String args[]){ 
    	Scanner s=new Scanner(System.in);
		PrintWriter out=new PrintWriter(System.out);
		int t=1;
        for(int tt=0;tt<t;tt++) {
        	long n=s.nextLong(),res=1,fact=1;
        	for(long i = 1;i <= n-1;i++){
        		res *= 2;
        		fact *= i;
        		fact %= MOD;
        		res %= MOD;
        	}
        	fact *= n;
        	//out.println(fact+" "+res);
        	fact %= MOD;
        	fact -= res;
        	fact %= MOD;
        	if(fact < 0)fact += MOD;
        	out.println(fact);
        }
	    s.close();
	    out.close();
    } 
    
    static void sort(long [] a) {
		ArrayList<Long> l=new ArrayList<>();
		for (long i:a) l.add(i);
		Collections.sort(l);
		for (int i=0; i<a.length; i++) a[i]=l.get(i);
	}
    static void sort(int [] a) {
		ArrayList<Integer> l=new ArrayList<>();
		for (int i:a) l.add(i);
		Collections.sort(l);
		for (int i=0; i<a.length; i++) a[i]=l.get(i);
	}
    static int gcd(int a, int b)
    {
      if (b == 0)
        return a;
      return gcd(b, a % b);
    }
    static void sortcol(long a[][],int c) {
		Arrays.sort(a, (x, y) -> {
			if(x[c]!=y[c])
			 return (int)( x[c] - y[c]);
			else {
				return (int)(x[1]-y[1]);
			}
		});
	}
    public static void printb(boolean ans) {
    	if(ans) {
    		System.out.println("YES");
    	}else {
    		System.out.println("NO");
    	}
    }
    
}
class pair implements Comparable<pair>{
	int a , b ; 
	pair(int x , int y){
		a=x;
		b=y;
	}
	public int compareTo(pair o) {
		return a != o.a ? a - o.a : b - o.b;
	}
}