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

//to increase stack size -Wl,--stack,8294304
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for(int i = a; i <= b; i++)
#define SQ(a) (a)*(a)
// a<<b means a*2^b and a>>b means a/2^b;
// to get the ith bit of a we do if((a&(1<<i))>0) then one else 0

ll m=1000000007;
vector<pair<ll,ll>> PrimeFactors(ll n)
{
    vector<pair<ll,ll>> factors;
    ll i=2;
    ll cnt=0;
    while(i<=sqrt(n) && n>1)
    {
        if(n%i==0)
        {
            n=n/i;
            cnt++;
        }
        else
        {
            if(cnt!=0)
            {
                factors.PB({i,cnt});
                cnt=0;
            }
            i++;
        }
    }
    if(cnt!=0)
    {
        factors.PB({i,cnt});
    }
    if(n!=1)
    {
        if(factors.size() && factors.back().first!=n)
        {
            factors.PB({n,1});    
        }
        else if(factors.size())
        {
            factors.back().second++;
        }
        else
        {
            factors.PB({n,1});
        }
    }
    return factors;
}
bool isPrime(ll a)
{
    if(a==1)
    {
        return false;
    }
    else if(a==2)
    {
        return true;
    }
    else if(a%2==0)
    {
        return false;
    }
    else
    {
        for(int i=3;i<=sqrt(a);i+=2)
        {
            if(a%i==0)
            {
                return false;
            }
        }
        return true;
    }
}
// time complexity is Nlog(logN) approx N
vector<ll> nPrimes(ll a)
{
    vector<ll> primes;
    ll Primes[a+1]={0};
    Primes[0]=0;
    Primes[1]=0;
    Primes[2]=1;
    primes.PB(2);
    for(int i=3;i<=a;i+=2)
    {
        Primes[i]=1;
    }
    for(int i=3;i<=a;i+=2)
    {
        if(Primes[i]==1)
        {
            primes.PB(i);
            for(int j=i*i;j<=a;j+=i)
            {
                Primes[j]=0;
            }
        }
    }
    return primes;
}
string toString(char x) 
{ 
    string s(1, x); 
    return s;    
}
ll fact(ll n)
{
    if(n==1 || n==0)
    {
        return 1;
    }
    else
    {
        return (n%m*fact(n-1)%m)%m;
    }
}
ll pow1(ll x,ll y)
{
    ll temp; 
    if( y == 0) 
        return 1; 
    temp = pow1(x, y/2); 
    if (y%2 == 0) 
        return (temp%m*temp%m)%m; 
    else
        return ((x%m*temp%m)%m*temp%m)%m; 
}
ll pow2(ll a,ll power)
{
    ll ans=1;
    while(power!=0)
    {
        if((power&1)==1)
        {
            ans*=a;
            
        }
        a=a*a;
        power=power>>1;
    }
    return ans;
}
// usefull for multiple Queries uses seive method 
vector<pair<ll,ll>> factorize(ll n,vector<ll> &Primes)
{
    vector<pair<ll,ll>> factors;
    ll i=0;
    ll p = Primes[i];
    ll cnt=0;
    while(p*p<=n)
    {
        if(n%p==0)
        {
            while(n%p==0)
                {
                    n=n/p;
                    cnt++;
                }
            factors.PB({p,cnt});
        }
        else
        {
            cnt=0;
            i++;
            p=Primes[i];
        }
    }
    if(n!=1)
    {
        factors.PB({n,1});
    }
    return factors;
}
ll getBit(ll n,ll i)
{
    if((n&(1<<i))>0)
    {
        return 1;
    }
    else
    {
        return 0;
    } 
}
void setBit(ll &n,ll i)
{
    n=(n|(1<<i));
}
void clearBit(ll &n,ll i)
{
    n=(n&(~(1<<i)));
}
void updateBit(ll &n,ll i,int j)
{
    if(j==0)
    {
        clearBit(n,i);
    }
    else
    {
        setBit(n,i);
    }
}
void clearLastIBits(ll &n,ll i)
{
    ll mask = ~ 0;
    mask = mask << i;
    n = ( n & mask );
}
void clearRangeIToJ(ll &n,ll i,ll j)
{
    // i is smaller value
    ll a = ~ 0 ;
    ll b = 1 << i   ;
    a = a << j+1;
    b = b-1;
    ll mask = a|b;
    n = (n & mask);
}

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    ll a[n+1];
    a[0]=1;
    for(int i=1;i<=n;i++)
    {
        a[i]=(a[i-1]%m*i%m)%m;
    }
    ll ans=(a[n]-pow1(2,n-1))%m;
    cout<<ans<<"\n";
    return 0;
}
// important Points

// {
    // sum of n num. in AP starting with a ending with b = n*(a+b)/2
    //sum of n num. in GP starting with a ending with b with factor k = b*k-a/(k-1)

    // BINARY SEARCH STL
    // binary_search(array,array+n,key) return true or false depending upon existence of key in array
    // lower_bound(array,array+n,key)-array; returns the index whose value is atleast equal to key
    // upper_bound(array,array+n,key)-array; returns the index whose value is just greater than key;
    // vector can also be used instead of array.

    // pop_back() removes the last element of a vector;
    // substr(starting index,no of elements); gives the substring of a string;

    // DATASTRUCTURE STL
    // unordered_map/set do things on average case O(1) while map/set in O(logn)
    // but the worst case i.e all the elements are same in unordered map in O(n) while in map is O(logn)

    /*set<data_type> s;
    s.insert(data);
    s.count(data); 1 if present 0 if not
    s.erase(data); removes the data
    s.size(); gives the size
    to iterate we need to use for(auto x : s)*/

    /*map<key,value> m;
    m[key]=value; inserts into map 
    m[key]; returns the value if exists
    m.count(key) if > 0 means the key exists;
    m.size(); size of map*/

    /*bitset<size> s(string); takes the binary string from right to left that is if 1010 is written then s[0] is 0 and s[1] is 1;
    bit operators can be directly used on them 
    s.count() gives no. of 1 in the array*/

    /*deque<datatype> d; maintain a dynamic array with front and back pointers with add and remove from both ends
    d.push_back(data);
    d.push_front(data);
    d.pop_back(data);
    d.pop_front(data);
    d.front();
    d.back();*/

    /*priority_queue<datatype> pq; always has the largest element on top
    pq.push(data);
    pq.top();
    pq.pop();
    to make it in increasing order we use priority_queue<datatype,vector<datatype>,greater<datatype>> pq;*/
// }