思路与算法

对合法起点(a,b)到终点(x,y)，无障碍且不越y=x的路径数为C(dx+dy,dy)-C(dx+dy,y-a-1)，第二项由反射原理得到。将障碍与终点按坐标排序，dp_i先取起点到i的合法路径数，再扣除dp_j乘j到i的合法路径数，按最早经过的障碍j分类。

正确性说明

反射把第一次越过山脊的路径与从反射起点出发的无约束路径一一对应，所以差值精确。任何坏路径有唯一首个障碍；dp_j只计此前无障碍的前缀，乘后缀覆盖并仅覆盖该类。按坐标顺序扣除所有首障碍类别，终点剩余数就是合法答案。

复杂度

预处理阶乘及逆阶乘O(N+logMOD)，障碍排序O(ClogC)，DP O(C²)，空间O(N+C)；初始化包含长2N的表，MOD=1e9+7且2N<MOD。

易错点

负组合下标或反向不可达返回0。任意两障碍之间也需保持山脊限制，不能只用普通网格组合数。起终点不允许障碍，按原题保证。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll P = 1000000007;
ll power(ll a, ll n) {
    ll z = 1;
    for (; n; n /= 2, a = a * a % P)
        if (n & 1)
            z = z * a % P;
    return z;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, C;
    cin >> N >> C;
    vector<pair<int, int>> p(C);
    for (auto &a : p)
        cin >> a.first >> a.second;
    p.push_back({N, N});
    sort(p.begin(), p.end());
    vector<ll> f(2 * N + 1, 1), iv(2 * N + 1, 1), dp(C + 1);
    for (int i = 1; i <= 2 * N; i++)
        f[i] = f[i - 1] * i % P;
    iv[2 * N] = power(f[2 * N], P - 2);
    for (int i = 2 * N; i; i--)
        iv[i - 1] = iv[i] * i % P;
    auto choose = [&](int n, int k) -> ll {
        return k < 0 || k > n ? 0 : f[n] * iv[k] % P * iv[n - k] % P;
    };
    auto ways = [&](pair<int, int> a, pair<int, int> b) {
        int dx = b.first - a.first, dy = b.second - a.second;
        if (dx < 0 || dy < 0)
            return 0LL;
        return (choose(dx + dy, dy) - choose(dx + dy, b.second - a.first - 1) + P) % P;
    };
    for (int i = 0; i <= C; i++) {
        dp[i] = ways({0, 0}, p[i]);
        for (int j = 0; j < i; j++)
            dp[i] = (dp[i] - dp[j] * ways(p[j], p[i]) % P + P) % P;
    }
    cout << dp[C] << '\n';
}