给定一个 $H*W$ 的棋盘，存在 $N$ 个黑色障碍格子。通过组合数学和动态规划的方法，计算从左上角到右下角的路径数，确保路径不经过障碍。利用容斥原理处理多个障碍，最终输出从起点到终点的路径总数。

欧拉函数 $ ext{varphi}(n)$ 表示小于等于 $n$ 且与 $n$ 互质的正整数个数。计算方法为质因数分解和容斥原理。若 $n = p^k$，则 $ ext{varphi}(n) = p^{k-1}(p-1)$；若 $n =  ext{prod}_{i=1}^{s}p_i^{k_i}$，则 $ ext{varphi}(n) = n  ext{prod}_{i=1}^s rac{p_i - 1}{p_i}$。欧拉函数具有积性，并可通过线性筛法高效计算。