\(H,W\) を 1 ずつデクリメントして縦に \(H\) 回移動、横に \(W\) 回移動する問題にしておきます。

上下の動かし方は \(\binom{2H}{H}\) 通りありますが、\(H\) 回の移動が終わったタイミングで同じ行に \(2\) 匹がいるということは変わりません。 以上より上下の動かし方は重要ではなく、\(H\) 行目で出会う場合についてのみ考えればよいです。

\(f(n)\) を \(2\) 匹が \(n\) 回ずつ右に移動、ラクダが \(H\) 回下に移動して \((H,n)\) ではじめて出会うような移動方法、として答えは \(\binom{2H}{H} \sum_{i=0}^{W} f(i)f(W-i)\) です。\(f\) を求めることを考えましょう。

\(g(n)\) を \(2\) 匹が \(n\) 回ずつ右に移動、ラクダが \(H\) 回下に移動して \((H,n)\) で(はじめてとは限らず)出会うような移動方法、とすると \(g(n) = \binom{2n}{n} \binom{2n+H}{H}\) と表せます。 \(C(n)\) をカタラン数として \(f(n) = g(n) - 2\sum_{i=0}^{n-1}g(i)C(n-i-1)\) です。

FFT を用いることで時間計算量 \(O(H+W \log W)\) で \(f\) を求めることができます。これは十分高速です。