考虑朴素的做法。共有 $\dbinom{n+m-2}{n-1}$ 条可行路径，而此时程序用时显然超出限制。

容易想到使用双向搜索处理。将行与列从 $1$ 开始进行编号。则可以以行号和列号之和为 $\left\lfloor\dfrac{n+m}2\right\rfloor+1$ 的格子作为分界线。第一次从左上角开始搜索，对于每个分界点，求出从左上角到达此格所有情况的路径异或和。第二次从右下角开始搜索，到达任意分界点时统计答案即可。

时间复杂度为 $2$ 的指数级。