x和y分开考虑，在（1,1）到（n，m）之间可以选择走i步。就需要选i步对应的行C（n-2，i）及i步对应的列C（m-2，i）。相乘起来。 假设$m\leq n$

$$\sum_{i=1}^{m-2} C_{n-2}^i\cdot C_{m-2}^i=\sum_{i=1}^{m-2} C_{n-2}^i\cdot C_{m-2}^{m-2-i}=C_{n+m-4}^{m-2}$$

然后标程里求i的阶乘的逆是预处理的，主要这句：

$$f[i]=(M-M/i)\cdot f[M\%i]\%M$$

这里f即i的逆元，为什么可以这么求呢？

首先这里的M必须是质数。

$$M=k\cdot i+r \equiv 0 \pmod M$$

两边乘上$i^{-1}\cdot r^{-1}$（如果M不是质数，r就可能为0）

$$\begin{eqnarray} k\cdot r^{-1}+i^{-1} &\equiv& 0 &\pmod M\\

i^{-1} &\equiv& -k\cdot r^{-1} &\pmod M\\

i^{-1} &\equiv& M-\left\lfloor\frac{M}{i}\right\rfloor\cdot \left(M\bmod i\right)^{-1} &\pmod M \end{eqnarray}$$

代码

#include
     
      #define M 1000000007#define N 200001#define ll long longll fac[N]={1,1},inv[N]={1,1},f[N]={1,1};int n,m;ll C(ll a,ll b){    return fac[a]*inv[b]%M*inv[a-b]%M;}int main(){    for(int i=2;i