F.小A的线段（hard version）

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

typedef long long ll;

#define X 2e5
#define M ((int)X)
#define N ((int)X + 10)
const ll mod = 998244353;

pair<int, int> ar[N];
map<pair<int, int>, ll> f[N];

void solve() {

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int a, b;
        cin >> a >> b;
        ar[i].first = a;
        ar[i].second = b;
    }
    sort(ar + 1, ar + m + 1);
    f[0][{0, 0}] = 1;
    for (int i = 1; i <= m; ++i) {
        f[i] = f[i - 1];
        for (auto item: f[i - 1]) {
            if (ar[i].first <= item.first.first + 1) {
                f[i][{max(min(ar[i].second, item.first.second), item.first.first),
                      max(ar[i].second, item.first.second)}] += item.second;
                f[i][{max(min(ar[i].second, item.first.second), item.first.first),
                      max(ar[i].second, item.first.second)}] %= mod;
            }

        }
    }
    cout << f[m][{n, n}] << endl;

}

int main() {

//int t;
//cin >> t;
//for(int u = 1; u <= t; u++)
    solve();


}