思路与算法

把向右记为R、向上记为U，任一路径有 $n$ 个R、$m$ 个U，共 $\binom{n+m}m$ 种。要求每个前缀R数不少于U数，即坐标满足 $x\ge y$。

对非法路径，找到第一次到达 $y=x+1$ 的位置，把这之前的R与U互换。原前缀U比R多1，交换后整条路径的总U数从 $m$ 变成 $m-1$，R数变为 $n+1$。这给出与含 $m-1$ 个U的普通路径的一一对应。因此合法数为

$$\binom{n+m}m-\binom{n+m}{m-1} =\binom{n+m}m\frac{n-m+1}{n+1}.$$

本题输出精确整数，不取模。程序手写基数 $10^9$ 的分段整数，通过依次乘 $n+i$、除 $i$（$i=1,\ldots,m$）计算组合数；每次除法都整除。再先乘 $n-m+1$、后除 $n+1$，得到最终整数。$n$ 不要求等于 $m$，不能只使用普通Catalan数公式。

正确性说明

非法路径第一次越过对角线时，必从平衡前缀走一步U而达到U比R多1。交换该前缀的两类步数，使总U减1、R加1。反向对任意具有 $n+1$ 个R、$m-1$ 个U的普通路径，因终点R严格多于U，存在第一次R比U多1的前缀，交换它即可恢复唯一非法路径。两次交换互为逆操作，故非法路径恰有第二个组合数那么多。

两项相减与乘比例形式代数等价。迭代第 $i$ 步后的大整数为 $\binom{n+i}i$，由组合递推知乘除保持精确；最终比例来自合法路径整数计数，因此最后也整除。分段小乘和从高位小除按基数进位、传余数保存精确值，最终输出正确。

复杂度

设中间大整数最多 $L$ 个基数 $10^9$ 的段。初始化为常数，$m$ 轮各进行一次 $O(L)$ 小乘和小除，最后两次运算及输出同为 $O(L)$。总时间 $O((m+1)L)$，额外空间 $O(L)$；没有建立 $n\times m$ 的大整数DP表。

易错点

1. 对角线上允许行走，禁止的是 $x<y$，反射用第一次差1的位置。
2. 输入为单组 $n,m$ 且 $n\ge m$，答案不是模数余数，也不是只在 $n=m$ 时成立的特式。
3. 最后先乘再除，不能提前整数除 $(n-m+1)/(n+1)$。
4. 小乘因子至10000、小除数至5001，用64位处理单段乘积和余数拼接；最高段不补零，其余段补9位。
5. 覆盖1×1、5000×1、5000×5000及近对角线非方形。独立答案用精确二项式差，并与465个小终点的受限网格DP核对。数据为非官方训练数据。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Big {
    static const unsigned BASE = 1000000000;
    vector<unsigned> d;
    Big() : d(1, 1) {
    }
    void multiply(unsigned value) {
        ll carry = 0;
        for (auto &v : d) {
            ll next = (ll)v * value + carry;
            v = next % BASE;
            carry = next / BASE;
        }
        while (carry) {
            d.push_back(carry % BASE);
            carry /= BASE;
        }
    }
    void divide(unsigned value) {
        ll remain = 0;
        for (int i = (int)d.size() - 1; i >= 0; i--) {
            ll next = remain * BASE + d[i];
            d[i] = next / value;
            remain = next % value;
        }
        assert(remain == 0);
        while (d.size() > 1 && d.back() == 0)
            d.pop_back();
    }
    void print() const {
        cout << d.back();
        for (int i = (int)d.size() - 2; i >= 0; i--)
            cout << setw(9) << setfill('0') << d[i];
        cout << '\n';
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    Big answer;
    for (int i = 1; i <= m; i++) {
        answer.multiply(n + i);
        answer.divide(i);
    }
    answer.multiply(n - m + 1);
    answer.divide(n + 1);
    answer.print();
}