感觉推出了 $O(nmT)$ 的柿子但不会化简。

思路是 $k=n+m-2$ 输出 $n+m-2 \choose n-1$；

$k=n+m-1$ 输出 ${n+m-2 \choose n-1}\times((n-1)m+(m-1)n-(n+m-2))$；

$k=n+m$ 时，发现对于格子 $(i,j)$，有 $2\times{i+j-2\choose i-1}\times{n-i+m-j-2\choose n-i-1}$ 种重复的情况，直接减掉后再加 $1$，答案是（这里令 $p$ 为墙的个数） ${n+m-2 \choose n-1}\times\dfrac{p(p-1)}2-2\times\sum\limits_{i=1}^{n-1}\sum\limits_{j=1}^{m-1} {i+j-2\choose i-1}\times{n-i+m-j-2\choose n-i-1}+(n-1)(m-1)$

不知道思路有没有问题