THT C (2021) permu

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int N = 1e5 + 5;
constexpr ll mod = 1e9 + 7;
pair<int, int> a[N], b[N];
ll gt[N], rgt[N];
int n, m, l(0);

void Read()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
        cin >> a[i].first >> a[i].second;
    sort(a + 1, a + m + 1);
}

ll Pow(ll a, ll b)
{
    ll ans(1);
    for (; b; b >>= 1)
    {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
    }
    return ans;
}

ll C(int k, int n)
{
    return gt[n] * rgt[k] % mod * rgt[n - k];
}

void Solve()
{
    gt[0] = 1;
    for (int i = 1; i <= n; ++i)
        gt[i] = gt[i - 1] * i % mod;
    rgt[n] = Pow(gt[n], mod - 2);
    for (int i = n - 1; ~i; --i)
        rgt[i] = rgt[i + 1] * (i + 1) % mod;

    int cnt(0);
    for (int i = 1, j = 1; i <= m; ++i)
    {
        int maxn = a[i].second;
        while (j <= m && maxn >= a[j].first)
        {
            maxn = max(maxn, a[j].second);
            ++j;
        }
        cnt += maxn - a[i].first + 1;
        i = j - 1;
    }

    ll ans(0);

    for (int i = 0; i <= cnt; ++i)
    {
        ans = (ans + ((i & 1) ? -1 : 1) * C(i, cnt) % mod * gt[n - i]) % mod;
    }

    cout << (ans + mod) % mod;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    Read();
    Solve();
}