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

#include <bits/stdc++.h>
using namespace std;
const long long MAX_VALUE = LONG_MAX;
const long long MIN_VALUE = LONG_MIN;
const unsigned long long U_MAX_VALUE = ULLONG_MAX;
long long gcd(long long a, long long b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
long long max(long long a, long long b) {
  if (a > b)
    return a;
  else
    return b;
}
long long min(long long a, long long b) {
  if (a < b)
    return a;
  else
    return b;
}
void sieve();
void solve(long long t);
void setPrimeList();
bool isPrimeN(long long n);
bool isInside(long long cr, long long cc, long long r, long long c);
long long modulo_multiplication(long long a, long long b, long long mod);
long long mod_power(long long x, unsigned long long y, long long p);
void bfs(long long s, vector<long long> adj[], bool visited[]);
const long long MAX_N = 1e5;
long long dp[MAX_N + 1];
const long long MOD = 1e9 + 7;
bool isPrime[MAX_N + 1];
vector<long long> primeList;
long long twoPow[31];
struct myComp {
  constexpr bool operator()(
      pair<long long, pair<long long, long long>> const& p1,
      pair<long long, pair<long long, long long>> const& p2) const noexcept {
    if (p1.second.first > p2.second.first)
      return false;
    else if (p1.second.first == p2.second.first) {
      if (p1.second.second < p2.second.second) {
        return false;
      } else {
        return true;
      }
    }
    return true;
  }
};
signed main() {
  ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  long long t = 1;
  long long tt = t;
  while (t--) {
    solve(tt - t);
    cout << "\n";
  }
}
long long isValley(long long arr[], long long n) {
  for (long long i = 1; i < n - 1; i++) {
    if (arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) {
      return true;
    }
  }
  return false;
}
unsigned long long fact(unsigned long long n) {
  unsigned long long ans = 1;
  for (unsigned long long i = 1; i <= n; i++) {
    ans = ans * i;
    ans %= 1000000007;
  }
  return ans;
}
unsigned long long power2(unsigned long long n) {
  unsigned long long ans = 1;
  for (unsigned long long i = 0; i < n; i++) {
    ans = ans * 2;
    ans %= 1000000007;
  }
  return ans;
}
void solve(long long t) {
  unsigned long long n;
  cin >> n;
  cout << (fact(n) - power2(n - 1)) % 1000000007;
}
void sieve() {
  memset(isPrime, true, sizeof(isPrime));
  for (long long i = 2; i <= MAX_N; i++) {
    if (isPrime[i]) {
      for (long long j = 2 * i; j <= MAX_N; j += i) {
        isPrime[j] = false;
      }
    }
  }
}
bool isPrimeN(long long n) {
  if (n == 1) return false;
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) return false;
  }
  return true;
}
void setPrimeList() {
  for (long long i = 2; i < MAX_N; i++) {
    if (isPrime[i] == true) {
      primeList.push_back(i);
    }
  }
}
long long mod_power(long long a, long long b, long long M = MOD) {
  long long res = 1;
  while (b) {
    if (b & 1) res = (res * a) % M;
    a = (a * a) % M;
    b >>= 1;
  }
  return res;
}
long long modulo_multiplication(long long a, long long b, long long mod) {
  long long res = 0;
  a %= mod;
  while (b) {
    if (b & 1) res = (res + a) % mod;
    a = (2 * a) % mod;
    b >>= 1;
  }
  return res;
}
void bfs(long long s, vector<long long> adj[], bool visited[]) {
  queue<long long> queue;
  visited[s] = true;
  queue.push(s);
  vector<long long>::iterator i;
  while (!queue.empty()) {
    s = queue.front();
    queue.pop();
    for (i = adj[s].begin(); i != adj[s].end(); ++i) {
      if (!visited[*i]) {
        visited[*i] = true;
        queue.push(*i);
      }
    }
  }
}
bool isInside(long long cr, long long cc, long long r, long long c) {
  if (cr < 0) return 0;
  if (cc < 0) return 0;
  if (cr >= r) return 0;
  if (cc >= c) return 0;
  return 1;
}
