考虑 DP。设 f _ i 为考虑完 [1, i]，强制选 i ，最少选多少点。枚举上一个选的点 j 进行转移，f _ i \gets f _ j + 1。
这个 j 需要满足什么条件，不存在某个路线 [a _ k, b _ k]，使得 j < a _ k < b _ k \le i（如果存在的话，这个区间没有被任何点覆盖）。也就是说，记 l _ i = \displaystyle \max _ {b _ k \le i} a _ k，要求 j \ge l _ i。
注意到转移形如单点修改，求区间 $\min$。使用线段树维护，可以优化到 $O(n \log n)$。
方案数可以相当容易地和最小值一起维护的。但需要注意的是，离散化后的一个点实际上相当于原图的一段区间，这一段区间中每个点是等价的，在转移后还要乘上区间长度。
```cpp
#include <bits/stdc++.h>
#define F(i, a, b) for(int i = (a); i <= (b); ++i)
#define dF(i, a, b) for(int i = (a); i >= (b); --i)
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int, LL> pii;
const int N = 1e6 + 5;
const int P = 1e9 + 7;
int m, n, a[N], b[N], k, c[N], l[N]; pii dp[N];
int Add(int x, int y) { return x + y >= P ? x + y - P : x + y; }
pii t[N << 2];
pii W(pii x, pii y) {
auto [tl, sl] = x; auto [tr, sr] = y;
if (tl < tr) return {tl, sl};
else if (tr < tl) return {tr, sr};
else return {tl, Add(sl, sr)};
}
void Pushup(int u) { t[u] = W(t[u << 1], t[u << 1 | 1]); }
void Update(int x, pii k, int l, int r, int u) {
if (l == r) return t[u] = k, void();
int mid = l + r >> 1;
if (x <= mid) Update(x, k, l, mid, u << 1);
else Update(x, k, mid + 1, r, u << 1 | 1);
Pushup(u);
}
pii Query(int ql, int qr, int l, int r, int u) {
if (ql <= l && r <= qr) return t[u];
int mid = l + r >> 1; pii res = {N, 0};
if (ql <= mid) res = W(res, Query(ql, qr, l, mid, u << 1));
if (qr > mid) res = W(res, Query(ql, qr, mid + 1, r, u << 1 | 1));
return res;
}
void mian() {
cin >> m >> n, c[1] = 0, c[k = 2] = m;
F(i, 1, n) cin >> a[i] >> b[i], c[++k] = a[i], c[++k] = b[i];
sort(c + 1, c + k + 1), k = unique(c + 1, c + k + 1) - c - 1;
F(i, 1, n)
a[i] = lower_bound(c + 1, c + k + 1, a[i]) - c,
b[i] = lower_bound(c + 1, c + k + 1, b[i]) - c - 1;
F(i, 1, k) l[i] = 1;
F(i, 1, n) l[b[i]] = max(l[b[i]], a[i]);
F(i, 1, k << 2) t[i] = {N, 0};
Update(1, dp[1] = {0, 1}, 1, k, 1);
int lim = 1;
F(i, 2, k - 1)
dp[i] = Query(lim, i - 1, 1, k, 1),
++dp[i].first, dp[i].second = 1ll * dp[i].second * (c[i + 1] - c[i]) % P,
Update(i, dp[i], 1, k, 1), lim = max(lim, l[i]);
dp[k] = Query(lim, k - 1, 1, k, 1);
cout << dp[k].first << " " << dp[k].second << "\n";
}
int main() {
// freopen("zyq.in", "r", stdin);
// freopen("zyq.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int _; cin >> _; while (_--) mian();
return 0;
}
```