歩き始めてから東に \(a\) 歩, 西に \(b\) 歩歩くのを二次元座標 \((b, a)\) にマッピングする.

\(k\) 歩歩いた結果ゴールにたどり着くためには, \(a+b = k,\ a-b=N\) となるので, \(a = (k+N)/2,\ b = (k-N)/2\) となる.

また, \(k\) 歩より前にゴールにたどり着いてはいけないので, \(a-b=N\) の線より上を歩いてはいけない. (踏むのもだめ)

これは, \(a-b=N-1\) の線より上を歩かずに (踏むのはOK), \(k-1\) 歩で \((b, a-1)\) にたどり着くことと同じである.

この組み合わせの数を \(f(k)\) とすると, カタラン数の計算方法 (\(a-b=N\) で折り返す) を応用して,

\[f(k) = \binom{a+b-1}{b} - \binom{a+b-1}{b-1}\]

となる. あとはこれをすべての \(k\) について計算すればいい.

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