这个东西有点太牛了，简单写一下。
煮波数学非常烂，所以大多数东西只能感性理解。
首先格路计数，从坐标 $ (0,0) $ 走到 $ (n,m) $ 的路径方案数（只能向右或向上走）为 $ C_{n+m}^{n} $。
考虑组合意义就是你的路径总长度为 $ n+m $，一共要向右走 $ n $ 次，相当于在一个 $ n+m $ 的序列上选 $ n $ 个位置向右走。
现在来看卡特兰数的一个公式 $ Catlan(n) = C_{2n}^n - C_{2n}^{n+1} $。
对着卡特兰数的定义：从 $ (0,0) $ 走到 $ (n,n) $ 且不越过 $ y=x $ 的方案数（即不经过 $ y=x+1 $ 的方案数）。
你考虑对于每一条经过 $ y=x+1 $ 的路径让它们与 $ y=x+1 $ 的第一个交点之后的所有部分关于 $ y=x+1 $ 对称，此时终点在 $ (n-1,n+1) $，那么总方案数即为 $ C_{2n}^{n-1} $。
即可得到卡特兰数的公式。
卡特兰数还有一个递推公式：$ Catlan(n) = \sum\limits_{i=1}^{n-1} Catlan(i) \times Catlan(n-i) $ 。
可以理解为枚举 $ y=x $ 上的每一个点 $ (i,i) $，总方案数即为 $ (0,0) $ 走到 $ (i,i) $ 再从 $ (i,i) $ 走到 $ (n,n) $ 的方案数相乘之和。
吼吼吼我会两条线的反射容斥了！！！
你考虑总方案数为到 $ (n,m) $ 的自由方案数 - 对分别碰到两条线进行容斥之后的方案数。
设两条线分别为 $ A $ 线和 $ B $ 线，每碰到一次 $ A $ 线就给序列增加一个 $ A \(，\) B $ 同理。
那么总的序列就形如 $ ABAABBAAAA \cdots $，把连续的 $ A $ 和 $ B $ 缩成一个之后，序列就是 $ AB $ 交替的了。
这样对 $ A $ 和 $ B $ 分别做一次容斥之后就可以得出答案。
参考代码：
inline void flip(pii &x,int b) {x={x.second-b,x.first+b};}pii pos={n+m+1,n};
int x=1,y=-m-2,res=idx(pos.first,pos.second),op=-1;
while (pos.first>=0 and pos.second>=0) {flip(pos,x),res=(res+idx(pos.first,pos.second)*op+mod)%mod,op*=-1;flip(pos,y),res=(res+idx(pos.first,pos.second)*op+mod)%mod,op*=-1;
}
x=1,y=-m-2,op=-1,pos={n+m+1,n};
while (pos.first>=0 and pos.second>=0) {flip(pos,y),res=(res+idx(pos.first,pos.second)*op+mod)%mod,op*=-1;flip(pos,x),res=(res+idx(pos.first,pos.second)*op+mod)%mod,op*=-1;
}
$ flip $ 函数是将 $ (x,y) $ 关于 $ y=x+b $ 对称。
主函数内的 $ x,y $ 分别是两条不能碰到的直线的截距 $ b_1 $ 和 $ b_2 $。