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;
using ll = long long;
int mod = (ll)1e9 + 7;
const int INF = 1e9 + 1;
const int N = 201;
const double eps = 1e-3;
template <typename XPAX>
void ckma(XPAX &x, XPAX y) {
  x = (x < y ? y : x);
}
template <typename XPAX>
void ckmi(XPAX &x, XPAX y) {
  x = (x > y ? y : x);
}
ll power(ll a, ll b) {
  if (!b) return 1;
  ll c = power(a, b / 2);
  c = (1LL * c * c);
  if (b % 2) c = (1LL * c * a);
  return c;
}
int mul(int a, int b) { return a * 1ll * b % mod; }
int add(int a, int b) {
  int s = (a + b);
  if (s >= mod) s -= mod;
  return s;
}
struct RMQ {
  vector<vector<int>> st;
  RMQ(vector<int> &a) {
    int n = a.size();
    int k = ceil(log2(n));
    st.clear();
    st = vector<vector<int>>(n, vector<int>(k + 1, 0));
    for (int i = 0; i < n; ++i) {
      st[i][0] = a[i];
    }
    for (int j = 1; j <= k; ++j) {
      for (int i = 0; i + (1 << j) <= n; ++i) {
        st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
      }
    }
  }
  int rng_q(int l, int r) {
    if (l > r) return -1;
    int j = log2(r - l + 1);
    int ans = max(st[l][j], st[r - (1 << j) + 1][j]);
    return ans;
  }
};
template <long long mod = 1000000007>
struct modint {
  long long a;
  modint() : a(0) {}
  modint(long long t) {
    a = t % mod;
    if (a < 0) a += mod;
  }
  operator long long() const { return a; }
  bool operator==(const modint &x) const { return a == x.a; }
  bool operator!=(const modint &x) const { return a != x.a; }
  modint operator-() const { return modint(a ? (mod - a) : 0); }
  modint operator~() const { return pow(mod - 2); }
  modint operator+(const modint &x) const { return modint(*this) += x; }
  modint operator-(const modint &x) const { return modint(*this) -= x; }
  modint operator*(const modint &x) const { return modint(*this) *= x; }
  modint operator/(const modint &x) const { return modint(*this) /= x; }
  modint &operator+=(const modint &x) {
    a += x.a;
    if (a >= mod) a -= mod;
    return *this;
  }
  modint &operator-=(const modint &x) {
    a -= x.a;
    if (a < 0) a += mod;
    return *this;
  }
  modint &operator*=(const modint &x) {
    a = a * x.a % mod;
    return *this;
  }
  modint &operator/=(const modint &x) {
    a = a * (~x).a % mod;
    return *this;
  }
  friend ostream &operator<<(ostream &os, const modint &x) { return os << x.a; }
  friend istream &operator>>(istream &is, modint &x) {
    long long t;
    is >> t;
    x = modint(t);
    return is;
  }
  modint pow(long long x) const {
    modint ret = 1, tmp = a;
    for (; x; tmp *= tmp, x >>= 1) {
      if (x & 1) ret *= tmp;
    }
    return ret;
  }
};
const ll MOD = 1e9 + 7;
using Mint = modint<MOD>;
template <class T>
struct Combination {
  vector<T> fact, factinv;
  Combination(int n) : fact(n + 1), factinv(n + 1) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * T(i);
    factinv[n] = ~fact[n];
    for (int i = n; i >= 1; i--) factinv[i - 1] = factinv[i] * T(i);
  }
  T nCr(int n, int r) {
    if (n < 0 || r < 0 || n < r) return 0;
    return fact[n] * factinv[r] * factinv[n - r];
  }
  T factorial(int x) {
    if (x < 0) return 0;
    return fact[x];
  }
};
int dp[N][N][N];
int a[N][N];
void done() {
  int n, k, p;
  cin >> n >> k >> p;
  vector<int> a(n);
  for (int i = 0; i < (n); ++i) {
    cin >> a[i];
  }
}
void solve() {
  int n;
  cin >> n;
  Mint ans = 1;
  for (int i = 1; i <= n; ++i) ans *= i;
  ans -= Mint(2).pow(n - 1);
  cout << ans << '\n';
}
void emer() {
  int n;
  cin >> n;
  vector<int> diamonds, miners;
  for (int i = 0; i < (2 * n); ++i) {
    int x, y;
    cin >> x >> y;
    if (x == 0) {
      miners.push_back(abs(y));
    } else
      diamonds.push_back(abs(x));
  }
  sort(miners.begin(), miners.end());
  sort(diamonds.begin(), diamonds.end());
  long double ans = 0;
  for (int i = 0; i < (n); ++i) {
    ans += (long double)sqrt(1ll * miners[i] * miners[i] +
                             1ll * diamonds[i] * diamonds[i]);
  }
  cout << std::fixed << std::setprecision(12) << (ans) << '\n';
}
void another() {
  int n, q;
  cin >> n >> q;
  vector<int> c(n);
  for (int i = 0; i < n; ++i) {
    cin >> c[i];
  }
  vector<vector<pair<int, pair<int, int>>>> qur(n);
  for (int i = 0; i < q; ++i) {
    int l, r;
    cin >> l >> r;
    --l;
    --r;
    qur[r].push_back({l, {i, 1}});
    if (l) {
      qur[l - 1].push_back({l, {i, -1}});
    }
  }
  vector<int> f(n);
  auto inc = [&](int x) {
    for (; x < n; x = (x | (x + 1))) f[x]++;
  };
  auto get = [&](int x) {
    int ans = 0;
    for (; x >= 0; x = (x & (x + 1)) - 1) ans += f[x];
    return ans;
  };
  vector<int> ret(q);
  map<int, int> last;
  vector<int> pev(n, -1);
  for (int i = 0; i < n; ++i) {
    if (last.count(c[i])) {
      pev[i] = last[c[i]];
    }
    last[c[i]] = i;
    inc(pev[i] + 1);
    for (auto c : qur[i]) {
      ret[c.second.first] += get(c.first) * c.second.second;
    }
  }
  for (int i = 0; i < (q); ++i) cout << ret[i] << '\n';
}
void test_case() {
  int t;
  cin >> t;
  for (int p = 0; p < (t); ++p) {
    cout << "Case #" << p + 1 << ": ";
    solve();
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}
