No.042 D

すべての経路の数から禁止区域を通る経路の数を引く.

以下上から $i$ 行目, 左から $j$ 列目のマスを $(i, j)$ とする. 左上は $(0, 0)$ である.

すべての経路の数は ${}_{H-1+W-1}C_{W-1}$ である.

禁止区域を通る経路であるが, 禁止区域に入るためには $(H-A-1, i) \rightarrow (H-A, i)$ ($0 \leq i \lt B$) の経路のどれかを必ず通る. この経路を通る組み合わせの数は $(0, 0) \rightarrow (H-A-1, i)$ の経路の数と $(H-A, i) \rightarrow (H-1, W-1)$ の経路の数の積となるので, ${}_{H-A-1+i}C_{i} \times {}_{A-1+W-1-i}C_{W-i-i}$ となる. これをすべての $i$ について計算して合計したものが禁止区域を通る経路の数である.

階乗および逆元はあらかじめ計算しておく.