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();
}