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

/*

Love has earth to which she clings  
With hills and circling arms about—  
Wall within wall to shut fear out.  
But Thought has need of no such things,  
For Thought has a pair of dauntless wings.
  
On snow and sand and turf, I see  
Where Love has left a printed trace  
With straining in the world’s embrace.  
And such is Love and glad to be.  
But Thought has shaken his ankles free.
  
Thought cleaves the interstellar gloom  
And sits in Sirius’ disc all night,  
Till day makes him retrace his flight,  
With smell of burning on every plume,  
Back past the sun to an earthly room.
  
His gains in heaven are what they are.  
Yet some say Love by being thrall  
And simply staying possesses all  
In several beauty that Thought fares far  
To find fused in another star. 

*/

#define JaiShreeRam

/*************************************************************************************************************************/
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")

using ll = long long;
using ld = long double;
using ull = __int64;
using st = string;

#define For(i, a, b) for (int i = a; i < b; i++)
#define Forl(i, size) for (int i = 0; i < size; i++)
#define Forr(i, size) for (int i = size - 1; i >= 0; i--)
#define ForR(i, a, b) for (int i = a; i >= b; i--)

#define cntd continue;
#define pb push_back
#define u_ unordered_
#define contd continue;
#define clr(a) memset(a, 0, sizeof(a));
#define all(c) (c).begin(), (c).end()

#define sz size()
#define mp make_pair
#define fi first
#define se second
#define ret return 0;
#define NIL -1

#define en cout << "\n";

#define sqrt sqrtl

#define beg begin()
#define rbeg rbegin()

#define ram(c, itr) for (__typeof((c).begin()) itr = (c).begin(); itr != (c).end(); itr++)
#define sita(c, itr) for (__typeof((c).rbegin()) itr = (c).rbegin(); itr != (c).rend(); itr++)

#define Bhaag_Milkha_Bhaag            \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<ull> vull;
typedef vector<string> vst;
typedef vector<bool> vb;
typedef vector<char> vch;
typedef vector<ld> vld;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

const ld Pi = 3.1415926535;
const long long Mod = 1e9 + 7;
const int N = 2 * 1e5 + 9;
const ll inf = (ll)2e18;
const ll ninf = (ll)-2e18;
const ll sInf = (ll)2e9;
const ll sNinf = (ll)-2e9;
const ld epsilon = (ld)1e-12;

ll sum = 0;
string res{};

vector<string> vec_splitter(string s)
{
    s += ',';
    vector<string> res;
    while (!s.empty())
    {
        res.push_back(s.substr(0, s.find(',')));
        s = s.substr(s.find(',') + 1);
    }
    return res;
}
void debug_out(vector<string> __attribute__((unused)) args, __attribute__((unused)) int idx) { cerr << endl; }
void debug_out(
    vector<string> __attribute__((unused)) args,
    __attribute__((unused)) int idx,
    __attribute__((unused)) int LINE_NUM) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T)
{
    if (idx > 0)
        cerr << ", ";
    else
        cerr << "Line(" << LINE_NUM << ") ";
    stringstream ss;
    ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, LINE_NUM, T...);
}
#define watch(x) cout << (#x) << " is " << (x) << endl;

#ifdef JaiShreeRam
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

bool mahadev(const pair<int, int> &a,
             const pair<int, int> &b)
{
    if (a.se == b.se)
        return (a.fi < b.fi);

    return (a.se < b.se);
}

template <class T>
bool ckmin(T &a, T &b)
{
    bool B = a > b;
    a = min(a, b);
    return B;
}
template <class T>
bool ckmax(T &a, T &b)
{
    bool B = a < b;
    a = max(a, b);
    return B;
}

ld getDist(ld x1, ld y1, ld x2, ld y2)
{
    return sqrtl((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

bool isPrime(ll num)
{
    bool flag = true;
    if (num == 1)
        return false;
    for (int i = 2; i <= sqrt(num); i++)
    {
        if (num % i == 0)
        {
            flag = false;
            break;
        }
    }
    return flag;
}

set<ll> fac;
void allFactors(ll n)
{
    for (ll i = 1; i <= sqrt(n); i++)
    {
        if (n % i == 0)
        {
            fac.insert(i);

            if (i != n / i)
            {
                fac.insert(n / i);
            }
        }
    }
    fac.insert(n);
}

ll findSum(ll a[], int l, int r)
{
    ll sum = 0;
    For(i, l, r)
    {
        sum += a[i];
    }
    return sum;
}

vector<pair<int, int>> vec1; //Prime Factors along with their exponents
void primeFactors(ll n)
{
    int c1 = 0;

    while (n % 2 == 0)
    {
        // printf("%d ", 2);
        n = n / 2;
        c1++;
    }
    if (c1)
        vec1.pb(mp(2, c1));
    c1 = 0;
    for (int i = 3; i <= sqrt(n); i = i + 2)
    {
        c1 = 0;
        while (n % i == 0)
        {
            // printf("%d ", i);

            n = n / i;
            c1++;
        }
        if (c1)
            vec1.pb(mp(i, c1));
    }
    c1 = 0;
    if (n > 2)
        vec1.pb(mp(n, 1));
}

ll power(int x, unsigned int y)
{
    ll temp;
    if (y == 0)
        return 1;
    temp = power(x, y / 2);
    if (y % 2 == 0)
        return temp * temp;
    else
        return x * temp * temp;
}

ll power(ll x, ll y, ll p)
{
    ll res = 1;

    x = x % p;
    if (x == 0)
        return 0;

    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % p;

        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

ull nCr(ll n, ll r)
{
    if (n == 0)
        return (ull)0;
    if (n < r)
        return ull(0);
    if (n == r)
        return (ull)1;

    ull p = 1;
    ull k = 1;
    if (n - r < r)
        r = n - r;

    if (r != 0)
    {
        while (r)
        {
            p *= n;
            k *= r;
            ll m = __gcd(p, k);
            p /= m;
            k /= m; //Simplifying
            n--;
            r--;
        }
    }
    else
        p = 1;

    return p;
}

ll lcm(ll a, ll b)
{
    return a / __gcd(a, b) * b;
}

unsigned int countBits(ll n, int specify)
{
    unsigned int count = 0, total = 0;
    if (n == 0)
    {
        if (specify == 1)
            return 0;
        else
            return 1;
    }
    while (n)
    {
        total += 1;
        count += n & 1;
        n >>= 1;
    }
    if (specify == 1)
        return count;
    else
        return (total - count);
}

ld angleClock(int hour, int minutes)
{
    long double hourAngle = (ld)((hour % 12) + minutes * (ld)1.0 / (ld)60) * (ld)30;
    long double minutesAngle = (ld)minutes * (ld)6;
    long double a = abs((ld)hourAngle - (ld)minutesAngle);
    long double b = (ld)360 - (ld)a;
    return a < b ? a : b;
}

int cntDig(ll n)
{
    return floor(log10(abs(n)) + 1);
}

//Seive of Eratosthenes

// const ll maxN = 1e7 + 9;
// vector<bool> pr((ll)1e7 + 9, true);
// vector<ll> pp;

// void seive()
// {
//     pr[0] = false;
//     pr[1] = false;
//     for (ll p = 2; p * p <= maxN; p++)
//     {
//         if (pr[p])
//         {
//             for (ll i = p * p; i <= maxN; i += p)
//             {
//                 pr[i] = false;
//             }
//         }
//     }
//     for (ll i = 0; i <= maxN; i++)
//     {
//         if (pr[i] == true)
//         {
//             // debug(i);
//             pp.pb(i);
//         }
//     }
// }

/*********************************************************************************************************************/
// Function and essential data structures For BFS In A Grid;
// int n, m, k;

// string s[509];
// int dr[] = {-1, 1, 0, 0};
// int dc[] = {0, 0, 1, -1};
// queue<int> rq, cq;
// bool vis[509][509] = {false};

// int cont = 0;
// bool ok = 0;

// void clearQ(std::queue<int> &q)
// {
//     std::queue<int> empty;
//     std::swap(q, empty);
// }

// bool valid(int i, int j)
// {
//     return (i >= 0 && i <= n - 1) && (j >= 0 && j <= m - 1);
// }

// void explore(int r, int c)
// {
//     int rr, cc;
//     for (int i = 0; i < 4; i++)
//     {   rr = r + dr[i];
//         cc = c + dc[i];

//         if (valid(rr, cc) && !vis[rr][cc] && s[rr][cc] == '#')
//         {
//             rq.push(rr);
//             cq.push(cc);
//             vis[rr][cc] = 1;
//         }
//     }
// }

// void bfsInGrid(int sr, int sc)
// {

//     clearQ(rq);
//     clearQ(cq);
//     clr(vis);
//     rq.push(sr);
//     cq.push(sc);
//     debug(sr, sc);
//     vis[sr][sc] = 1;
//     while (!rq.empty() && !cq.empty())
//     {

//         int r = rq.front();
//         rq.pop();
//         int c = cq.front();
//         cq.pop();
//         explore(r, c);
//     }
// }

/*******************************************************************************************************************************************/
// #define SIZE 100009
// ll fact[SIZE] = {0};

// void factorial()
// {
//     int i;
//     fact[0] = 1;
//     for (i = 1; i <= SIZE; i++)
//     {

//         // Calculation of factorial
//         // As fact[i-1] stores the factorial of n-1
//         // so factorial of n is fact[i] = (fact[i-1]*i)
//         fact[i] = (fact[i - 1] * i) % Mod;
//     }
// }

void scar(ll a[], int n, int param = 0)
{
    if (param == 0)
    {
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
    }
    else
    {
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
        }
    }
}

/*******************************************************************************************************************************************/

signed main()
{
    Bhaag_Milkha_Bhaag

        //seive();

        // TO Enable or Disable Debuuging Go To the Top;
        string aux1{},
        aux2{}, aux3{};

    ll T = 1;

    // cin >> T;

    For(_____, 1, T + 1)
    {
        int f = 0, fl1 = 0, fl2 = 0, u = 0, v = 0, w = 0, c1 = 0, c2 = 0, cont = 0, cnt = 0, c3 = 0, auxi = 0, auxj = 0;
        ll mi = inf, le = 0;
        ll ma = ninf, sol = 0;
        int n;
        cin>>n;
        ll fact=1;
        For(i,1,n+1)
        {
            fact=((fact%Mod)*(i%Mod))%Mod;
        }
        fact%=Mod;
        ll po=power(2,n-1,Mod);
        po%=Mod;
        cout<<(fact-po)%Mod<<endl;

    }
    return 0;
}

//*********************** PAY ATTENTION **********************************//
/*

Always remember, SPAGHETTI Code is the worst thing you can ever come up with!

------------
Even If You PASS The PRETESTS, Don't Be HAPPY (Don't even SMILE)!!
Your solution might fail in SYSTEM TESTS..!!
.
.
. 
Surprise MADAFAKA !!
-------------


*/
//*************************************************************************//