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

public class ct1 {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
            left=null;
            right=null;
        }
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public static List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        ArrayList<String> a = new ArrayList<>();
        for(int i=0; i<strs.length; i++){
            int f=0, j=0;
            for(j=0; j<a.size(); j++){
                char[] x = strs[i].toCharArray();
                Arrays.sort(x);
                String temp = new String(x);
                if(temp.equals(a.get(j))){
                    f=1;
                    break;
                }
            }
            if(f==1){
                res.get(j).add(strs[i]);
            }
            else{
                ArrayList<String> tt = new ArrayList<>();
                char[] x = strs[i].toCharArray();
                Arrays.sort(x);
                String temp = new String(x);
                tt.add(temp);
                res.add(tt);
            }
        }
        return res;
    }


    static class pair{
        int val, count;
        pair(int val, int count){
            this.val = val;
            this.count = count;
        }
    }
    static int m = 1000000007;

    static long fact(int n){
        long res=  1;
        for(int i=2; i<=n; i++){
            res = (res*i)%m;
        }
        return res;
    }

    static long power(int n){
        if(n==1)
            return 2;
        if(n%2==0){
            long x = power(n/2)%m;
            return (x*x)%m;
        }
        return (2*(power(n-1))%m)%m;
    }

    public static void main(String[] args) {
        Scanner inp = new Scanner(System.in);
        int x=inp.nextInt();
        long res = ((fact(x) - power(x-1) + m)%m);
        System.out.println(res);
    }

    static class Interval{
        int start, end;
        Interval(int start, int end){
            this.end= end;
            this.start = start;
        }
    }

    static class sort implements Comparator<Interval>{
        public int compare(Interval i1, Interval i2){
            return i1.start - i2.start;
        }
    }
    public static int minMeetingRooms(List<Interval> intervals) {
        Collections.sort(intervals, new sort());
        ArrayList<Interval> a = new ArrayList<>();
        a.add(intervals.get(0));
        for(int i=1; i<intervals.size(); i++){
            boolean added = false;
            for(int j=0; j<a.size(); j++){
                if(a.get(j).end <= intervals.get(i).start){
                    a.set(j, intervals.get(i));
                    break;
                }
            }
            if(!added){
                a.add(new Interval(intervals.get(i).start, intervals.get(i).end));
            }
        }
        return a.size();
    }

    static int bs(int[] n, int s, int e){
        if(s>=e)
            return n[s];
        int middle = (s+e)/2;
        if(s!=0 && n[s-1]>n[s])
            return n[s];
        else if(n[e]<n[s])
            return bs(n, middle+1, e);
        else
            return bs(n, s, middle-1);
    }

    public static int findMin(int[] nums) {
        return bs(nums, 0, nums.length-1);
    }

    public static int subarraySum(int[] nums, int k) {
        int res = 0, csum=0, i=0, j=0;
        csum+=nums[j];
        while(j<nums.length){
            if(i>j){
                j=i;
                if(j>nums.length)
                    break;
                csum = nums[i];
            }
            else if(csum == k){
                res++;
                csum-=nums[i];
                i++;
            }
            else if(csum<k){
                j++;
                if(j<nums.length){
                    csum+=nums[j];
                }
            }
            else if(csum>k){
                csum-=nums[i];
                i++;
            }
        }
        return res;
    }

    public static int firstUniqChar(String s) {
        LinkedHashMap<Character, Integer> a = new LinkedHashMap<>();
        for(int i=0; i<s.length(); i++){
            if(a.get(s.charAt(i))==null){
                a.put(s.charAt(i), 1);
            }
            else{
                a.put(s.charAt(i), a.get(s.charAt(i))+1);
            }
        }
        for(Map.Entry<Character, Integer> ss:a.entrySet()){
            if(ss.getValue().equals(1))
                return (char)(ss.getKey());
        }
        return -1;
    }

    static class KthLargest {

        TreeMap<Integer, Integer> tm = new TreeMap<>();
        int k =0;
        public KthLargest(int k, int[] nums) {
            this.k = k;
            for(int i=0; i<nums.length; i++){
                if(tm.get(nums[i]) == null){
                    tm.put(nums[i], 1);
                }
                else{
                    tm.put(nums[i], tm.get(nums[i])+1);
                }
            }
        }

        public int add(int val) {
            if(tm.get(val) == null){
                tm.put(val, 1);
            }
            else{
                tm.put(val, tm.get(val)+1);
            }
            ArrayList<Integer> y = new ArrayList<>();
            int temp = 0;
            temp+=(k-1);
            int res = 0;
            while(temp-->0){
                int x = tm.lastKey();
                if(tm.get(x) == 1){
                    y.add(x);
                    tm.remove(x);
                }
                else{
                    tm.put(x, tm.get(x)-1);
                }
            }
            res = tm.lastKey();
            for(int i=0; i<y.size(); i++){
                if(tm.get(y.get(i)) == null){
                    tm.put(y.get(i), 1);
                }
                else{
                    tm.put(y.get(i), tm.get(y.get(i))+1);
                }
            }
            return res;
        }
    }

    static long binaryToDecimal(String n)
    {
        String num = n;
        long dec_value = 0;

        // Initializing base value to 1,
        // i.e 2^0
        long base = 1;

        int len = num.length();
        for (int i = len - 1; i >= 0; i--) {
            if (num.charAt(i) == '1')
                dec_value += base;
            base = base * 2;
        }

        return dec_value;
    }


    static HashSet<String> a = new HashSet<>();
    static HashSet<Integer> b = new HashSet<>();
    public static boolean wordBreak(String s, List<String> w) {
        for(int i=0; i<w.size(); i++){
            a.add(w.get(i));
        }
        return res(s, 0, s.length());
    }

    static boolean res(String s, int i, int j){
        if(a.contains(s.substring(i, j)))
            return true;
        if(b.contains(i))
            return true;
        for(int k=i+1; k<j; k++){
            if(a.contains(s.substring(0, k)))
                if(res(s, k, j)){
                    b.add(i);
                    return true;
                }
        }
        return false;
    }




}