下に進むことのできないマスの組が与えられたとき、\((N,M)\) にたどり着けるかの判定は、「下に進める時は下に進み、そうでない時は右に進む」ということを繰り返せばよいです。

\(N=1\) の場合、解は \(1\) です。以降 \(2 \le N\) とします。

上記の貪欲法を行い、最後に行った下のマスへの移動が \((N-1,i)\) から \((N,i)\) への移動であるようなものの個数を求めます。

そのような個数は、以下を全かけ合わせることで求めることができます。

• \((1,1)\) から \((N-1,i)\) への経路数 \(\displaystyle \binom{N+i-3}{i-1}\)
• 下へ行くことのできるか不定であるマスの個数 \(X\) に対する \(2^X\)

上記の \(X\) は、貪欲法において右に進んだ \(i-1\) マスと下に進んだ \(N-1\) マス以外の全てのマスを数え上げるため \(X=(N-1)M-(N-1)-(i-1)\) です。

以上より、本問題を \(\mathrm{O}(N+M)\) で解くことができます。