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;

#define ll long long
#define ld long double
vector<ll>v;

bool isPrime(ll n) 
{ 
    // Corner cases 
    if (n <= 1) 
        return false; 
    if (n <= 3) 
        return true; 
  
    // This is checked so that we can skip 
    // middle five numbers in below loop 
    if (n % 2 == 0 || n % 3 == 0) 
        return false; 
  
    for (ll i = 5; i * i <= n; i = i + 6) 
        if (n % i == 0 || n % (i + 2) == 0) 
            return false; 
  
    return true; 
} 

unsigned ll factorial(unsigned ll n) 
{ 
    if (n == 0) 
        return 1; 
    return n * factorial(n - 1); 
} 
ll gcd(ll a, ll b)
{
  if (b == 0)
    return a;
  return gcd(b, a % b);
}
// function for power 
float power(float x, ll y)  
{  
    float teunordr_map;  
    if(y == 0)  
        return 1;  
    teunordr_map = power(x, y / 2);  
    if (y % 2 == 0)  
        return teunordr_map * teunordr_map;  
    else
    {  
        if(y > 0)  
            return x * teunordr_map * teunordr_map;  
        else
            return (teunordr_map * teunordr_map) / x;  
    }  
}  
// Function to return LCM of two numbers 
ll lcm(ll a, ll b)
{
    return (a / gcd(a, b)) * b;
}

void permutation(ll n, ll x){
    if(n==0)
        return ;
    ll x1=x*10+4, x2=x*10+7;
    v.push_back(x1);
    v.push_back(x2);
    permutation(n-1, x1);
    permutation(n-1, x2);
}  
bool is_lucky(ll n){
    while(n){
        ll rem=n%10;
        if(rem!=4 && rem!=7){
            return 0;
        }
        n/=10;
    }
    return 1;
}

void SieveOfEratosthenes(ll n) 
{ 
    // Create a boolean aay "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (ll p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (ll i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Prll all prime numbers 
    for (ll p=2; p<=n; p++) 
       if (prime[p]) 
          v.push_back(p);
} 
vector<ll> prllNGE(vector<ll> arr) 
{ 
    ll n=arr.size();
    stack<ll> s; 
  
    vector<ll>arr1(n,0);
  
    // iterating from n-1 to 0 
    for (ll i = n - 1; i >= 0; i--)  
    { 
        /*We will pop till we get the  
        greater element on top or stack gets empty*/
        while (!s.empty() && arr[s.top() ]<= arr[i]) 
            s.pop(); 
  
        /*if stack gots empty means there  
        is no element on right which is greater  
        than the current element. 
        if not empty then the next greater  
        element is on top of stack*/
        if (s.empty())  
            arr1[i] = -1;          
        else 
            arr1[i] = s.top();         
  
        s.push(i); 
    } 
  return arr1;
    
} 
map<ll,ll> odd_divisors(ll n){
    map<ll,ll>mp;
    while(n%2==0){
        mp[2]++;
        n=n/2;
    }
    for(ll i=3; i<=sqrt(n); i+=2){
        while(n%i==0){
            n=n/i;
            mp[i]++;
        }
    }
    if(n>2) mp[n]++;
    return mp;
}
ll smallest_divisor(ll n){
    for(ll i=2; i<=sqrt(n); i++){
        if(n%i==0) return i;
    }
    return n;
}
ll nCr(ll n, ll r)
{
 
    // p holds the value of n*(n-1)*(n-2)...,
    // k holds the value of r*(r-1)...
    ll p = 1, k = 1;
 
    // C(n, r) == C(n, n-r),
    // choosing the smaller value
    if (n - r < r)
        r = n - r;
 
    if (r != 0) {
        while (r) {
            p *= n;
            k *= r;
 
            // gcd of p, k
            long long m = __gcd(p, k);
 
            // dividing by gcd, to simplify
            // product division by their gcd 
            // saves from the overflow
            p /= m;
            k /= m;
 
            n--;
            r--;
        }
 
        // k should be simplified to 1
        // as C(n, r) is a natural number
        // (denominator should be 1 ) .
    }
 
    else
        p = 1;
 
    // if our approach is correct p = ans and k =1
    return p;
}
ll nCrModpDP(ll n, ll r, ll p) 
{ 
    // The array C is going to store last row of 
    // pascal triangle at the end. And last entry 
    // of last row is nCr 
    ll C[r+1]; 
    memset(C, 0, sizeof(C)); 
  
    C[0] = 1; // Top row of Pascal Triangle 
  
    // One by constructs remaining rows of Pascal 
    // Triangle from top to bottom 
    for (ll i = 1; i <= n; i++) 
    { 
        // Fill entries of current row using previous 
        // row values 
        for (ll j = min(i, r); j > 0; j--) 
  
            // nCj = (n-1)Cj + (n-1)C(j-1); 
            C[j] = (C[j] + C[j-1])%p; 
    } 
    return C[r]; 
} 
ll nCrModpLucas(ll n, ll r, ll p) 
{ 
   // Base case 
   if (r==0) 
      return 1; 
  
   // Compute last digits of n and r in base p 
   ll ni = n%p, ri = r%p; 
  
   // Compute result for last digits computed above, and 
   // for remaining digits.  Multiply the two results and 
   // compute the result of multiplication in modulo p. 
   return (nCrModpLucas(n/p, r/p, p) * // Last digits of n and r 
           nCrModpDP(ni, ri, p)) % p;  // Remaining digits 
} 
// Driver Program to test above function 
unsigned long long factorial_MOD(ll n)
{
    const unsigned ll M = 1000000007;
    unsigned long long f = 1;
 
    for (ll i = 1; i <= n; i++){
        f = ((i%M)*(f%M))%M;
    }  // WRONG APPROACH as
                    // f may exceed (2^64 - 1)
 
    return f % M;
}
ll buy_iceSphere(ll m, int a[], ll n){
    ll ans=0;
    int i=0,j=m;
    while(i<m && j+1<n){
        if(a[i]<a[j] && a[i]<a[j+1]) i++,j++, ans++;
        else j++;
    }
    return ans;
}
 long double nthRoot(long A, long N) 
{ 
    // intially guessing a random number between 
    // 0 and 9 
     long double xPre = rand() % 10; 
  
    //  smaller eps, denotes more accuracy 
     long double eps = 1e-3; 
  
    // initializing difference between two 
    // roots by INT_MAX 
     long double delX = INT_MAX; 
  
    //  xK denotes current value of x 
     long double xK; 
  
    //  loop untill we reach desired accuracy 
    while (delX > eps) 
    { 
        //  calculating current value from previous 
        // value by newton's method 
        xK = ((N - 1.0) * xPre + 
              ( long double)A/pow(xPre, N-1)) / ( long double)N; 
        delX = abs(xK - xPre); 
        xPre = xK; 
    } 
  
    return xK; 
} 

int main()
{
     unsigned ll n;
    cin>>n;
    ll t1 =factorial_MOD(n);
    ll t2=1;
    ll mod=1000000007;
    for(int i=1;i<n;i++){
        t2 = (t2%mod)*2;
        t2=t2%mod;
    }
    cout<<t1-t2<<endl;
    
}