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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class C1391 {
    static List<String>L;
    static int cnt =0;
    static void permute(String str, int l, int r)
    {
        if (l == r)
            L.add(str);
            //System.out.println(str);
        else
        {
            for (int i = l; i <= r; i++)
            {
                str = swap(str,l,i);
                permute(str, l+1, r);
                str = swap(str,l,i);
            }
        }
    }

    static String swap(String a, int i, int j)
    {
        char temp;
        char[] charArray = a.toCharArray();
        temp = charArray[i] ;
        charArray[i] = charArray[j];
        charArray[j] = temp;
        return String.valueOf(charArray);
    }

    static void solve(int a[], int n){
        int count = 0;
        for (int i=1;i<n;++i){
            for (int j=i-1;j>=0;--j){
                if (a[j] > a[i]){
                    count++;
                    //System.out.println((i+1) + " " + (j+1));
                    break;
                }
            }
        }
        for (int i=0;i<n-1;++i){
            for (int j=i+1;j<n;++j){
                if (a[j] > a[i]){
                    count++;
                    //System.out.println((i+1) + " " + (j+1));
                    break;
                }
            }
        }
        if (count>n-1){
            cnt++;
            //System.out.println(Arrays.toString(a));
        }
    }


    static long power(long x, long y, long p)
    {
        long res = 1;
        x = x % p;

        if (x == 0) return 0; // In case x is divisible by p;

        while (y > 0)
        {
            if((y & 1)==1)
                res = (res * x * 1L) % p;

            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //String in[] = br.readLine().trim().split(" ");
//        L =  new ArrayList<>();
//        String str = "12345";
//        int n = str.length();
//        permute(str, 0, n-1);
//
//        int a[];
//
//        for (String e:L){
//            a = new int[5];
//
//            a[0] = e.charAt(0) - '0';
//            a[1] = e.charAt(1) - '0';
//            a[2] = e.charAt(2) - '0';
//            a[3] = e.charAt(3) - '0';
//            a[4] = e.charAt(4) - '0';
//            //a[5] = e.charAt(5) - '0';
//            //System.out.println(Arrays.toString(a));
//            solve(a, 5);
//            //System.out.println("\n");
//            //System.out.println(a[0]);
//        }
//        System.out.println(cnt);



        int n = Integer.parseInt(br.readLine());

        long mod = 1000000007L;
//        for (int i=1;i<100;++i){
//
//            System.out.println(pw);
//        }
        long pw = power(2, n-1, mod);

        long fact = 1L;

        for (int i=1;i<=n;++i){
            fact = (fact * i) % mod;
        }

        long ans = fact - pw;
        if (ans > mod){
            ans -= mod;
        }
        //int pw = power(2, n-1, mod);

        System.out.println(ans);

        //n! - ceiling(2^(n-1))

    }
}
