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>
#define ll long long int
#define fr0(i,n) for(ll i=0;i<n;i++)
#define fr1(i,n) for(ll i=1;i<=n;i++)
#define fr(i,a,b) for(ll i=a;i<b;i++)
#define frd(i,a,b) for(ll i=a;i>=b;i--)
#define  pb push_back
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define all(a) a.begin(),a.end()
#define vi vector <int>
#define vs vector <string>
#define vc vector <char>
#define vl vector <ll>
#define vp vector<pair<ll,ll>>
#define take(v,n)  fr0(i,n){ll num; cin>>num; v.pb(num); }
#define inf 1e18+23
#define mp make_pair 
#define M 1000000007 
#define YES cout<<"YES"
#define NO cout<<"NO"
#define sh(v) for(auto x:v)cout<<x<<" "
#define sh1(ele) cout<<ele<<" "
#define nl cout<<endl
#define ff first 
#define ss second 
#define stre string
#define br break
#define con continue
#define sortd(v) sort(all(v), greater<int>()); 
inline ll gcd(ll a ,ll b)
{if(b==0) return a;a%=b;return gcd(b,a);}
#define cn(x) ll(x); cin>>x

//ll lcm(ll a, ll b){return a*b/__gcd(a, b);}
// ll power(ll a, ll b){ll ans = 1;while(b){if(b&1) ans = ans*a; b/=2;a=a*a;}return ans;}
//ll inverse(ll a, ll m){ll m0 = m; ll y = 0, x = 1; if (m == 1) return 0;while (a > 1)
//{  ll q = a / m; ll t = m;  m = a % m, a = t;  t = y;   y = x - q * y;   x = t;}if (x < 0) x += m0; return x;}
//ll nCr(ll n, ll r){if(r > n) return 0; else return ((fact[n]%mod*inverse(fact[r], mod)%mod)%mod*inverse(fact[n-r], mod)%mod)%mod;}
using namespace std;
ll lcm(ll a, ll b){
    return a / __gcd(a, b) * b;
}
bool sortbysec(const pair<int,int> &a, 
              const pair<int,int> &b) 
{ 
    return a.second<b.second;
} 
ll max(ll a,ll b){
    if(a>=b)return a;
    else return b;
}


ll SD(ll n){
    for(ll i=2;i<=sqrt(n);i++){
        if(n%i==0)return i;
    }
    return n;
    
}

bool prime(ll n){
    for(ll i=1;i<=sqrt(n);i++){
        if(n%i==0)return false;
    }
    return true;
}
ll res=0;
int vis[200027]={0};
vector<vector<ll>> g(200027);

void dfs(ll i){
    int flag=1;
    vis[i]=1;
    
    for(auto x:g[i]){
       
        if(!vis[x]){
             flag=0;
            if(g[x].size()!=0)
            dfs(x);
            
            
        }
    }
    if(flag)return;
}

void solve(){
cn(n);
ll fac=1;
ll po=2;
for(ll i=2;i<=n;i++){
    fac*=i;
    fac%=M;
    if(i<=n-1){
    po*=2;
    po%=M;
    }
    
}
cout<<fac%M-po%M;

}

 int main() {
    ios_base::sync_with_stdio(0);
	cin.tie(NULL);cout.tie(NULL);
	ll t1;//cin>>t1;
  t1=1;
   

	while(t1--){
    solve();
    nl;
	}

}
	
	