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.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class C {

   private static final String INPUT_FILE_PATH = "";

   private static final int MOD = 1000000007;

   private static long[] fact;
   private static long[] factInv;

   private static int euclid(int a, int mod) {
      int xPrev = 1;
      int x = 0;
      int yPrev = 0;
      int y = 1;

      int p = MOD;
      int q;
      int temp;
      while (p > 0) {
         q = a / p;

         temp = x;
         x = xPrev - q * x;
         xPrev = temp;

         temp = y;
         y = yPrev - q * y;
         yPrev = y;

         temp = a;
         a = p;
         p = temp % p;
      }

      return (xPrev + mod) % mod;
   }

   private static void precompute(int n) {
      fact = new long[n + 1];
      factInv = new long[n + 1];
      fact[0] = fact[1] = factInv[0] = factInv[1] = 1;
      for (int i = 2; i <= n; i++) {
         fact[i] = (i * fact[i - 1]) % MOD;
         factInv[i] = euclid((int) fact[i], MOD);
      }
   }

   private static long choose(int n, int k) {
      long res = fact[n];
      res *= factInv[k];
      res %= MOD;
      res *= factInv[n - k];
      res %= MOD;
      return res;
   }

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

      precompute(n);

      long ans = 0;
      for (int i = 0; i < n; i++) {
         ans += choose(n - 1, i);
         ans %= MOD;
      }
      ans = (fact[n] - ans + MOD) % MOD;

      out.println(ans);
   }

   public static void main(String[] args) throws Exception {
      InputStream inputStream = INPUT_FILE_PATH.isEmpty()
         ? System.in
         : new FileInputStream(new File(INPUT_FILE_PATH));
      OutputStream outputStream = System.out;

      InputReader inputReader = new InputReader(inputStream);
      PrintWriter printWriter = new PrintWriter(outputStream);

      solve(inputReader, printWriter);

      printWriter.close();
   }

   private static class InputReader {
      private BufferedReader bufferedReader;
      private StringTokenizer stringTokenizer;

      public InputReader(InputStream inputStream) {
         this.bufferedReader = new BufferedReader(new InputStreamReader(inputStream), 32768);
         this.stringTokenizer = null;
      }

      public String nextToken() {
         while (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
            try {
               stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            } catch (IOException e) {
               throw new RuntimeException(e);
            }
         }
         return stringTokenizer.nextToken();
      }

      public int nextInt() {
         return Integer.parseInt(nextToken());
      }

      public long nextLong() {
         return Long.parseLong(nextToken());
      }

      public double nextDouble() {
         return Double.parseDouble(nextToken());
      }
   }
}
