writer による解法：https://atcoder.jp/contests/arc124/editorial/2314

とほとんど同じですが、\(O(H+W)\) 時間計算量で解けるため、それを解説しておきます。

最後に \(\binom{2H}{H}\) 倍することにして、次の形の問題に帰着されます。

• はじめ \((-H,0)\) にいる
• \((+1,0)\), \((0,+1)\), \((0,-1)\) の \(3\) 方向への移動を \(2H, W, W\) 回行う
• \((0,0)\) をちょうど \(1\) 度通るのは何通りか？

\(f, g, h\) を以下のように定めます。\(f, g\) については writer 解説と同一のものです。

• \(f(n)\)：\(y\) 方向への移動を \(n\) 回ずつ使ってはじめて \((0,0)\) に辿り着く方法の数え上げ
• \(g(n)\)：\(y\) 方向への移動を \(n\) 回ずつ使って \((0,0)\) に辿り着く方法の数え上げ（はじめてとは限らない）
• \(h(n)\)：\((0,0)\) を出発して、\(y\) 方向への移動を \(n\) 回ずつ使って \((0,0)\) に辿り着く方法の数え上げ

次は簡単に求まります。

• \(g(n) = \frac{(H+2n)!}{H!n!n!}\)
• \(h(n) = \frac{(2n)!}{n!n!}\)

また、\(g(n)\) の数え上げを、初めて \((0,0)\) に到達するタイミングで場合分けして立式することにより、 \(g(n) = \sum_{i}f(i)h(n-i)\) が成り立つことが分かります。

母関数 \(F(x) = \sum_{n=0}^{\infty} f(n)x^n\), \(G(x) = \sum_{n=0}^{\infty} g(n)x^n\), \(H(x) = \sum_{n=0}^{\infty} h(n)x^n\) を考えれば、この関係式は \(G(x) = F(x)H(x)\) と表すことができます。したがって、\(F(x) = G(x) / H(x)\) です。

求めるものは、\([x^W] F(x)^2 = [x^W] G(x)^2/H(x)^2\) です。有理数に対する二項定理 \((1+x)^{r} = \sum_{n=0}^{\infty}\binom{r}{n}x^n\) などにより \(H(x) = (1-4x)^{-1/2}\) が成り立つので、

\([x^W] F(x)^2 = [x^W] G(x)^2(1-4x) = [x^W]G(x)^2 - 4[x^{W-1}]G(x)^2\)

と変形できます。結局 \(G(x)^2\) の \(W-1\), \(W\) 次の係数が分かればよく、これらは（FFT不要で）線形時間で計算できます。