初めに、縦方向の移動と横方向の移動は独立です。
縦方向の移動を $i$ 回と決め打った時の $\left( x_2,y_2 \right)$ への移動方法を求めることを考えます。各移動がどちらの方向の移動かは ${}_K C_{i}$ 通りです。 $i$ 回の縦方向での移動、 $K-i$ 回の横方向の移動がそれぞれ何通りかを求められればよいです。
これは以下の小問題のように考えることができます。

変数 $A$ があり、現在 $A=S$ が成立している。以下の操作をちょうど $i$ 回繰り返して $A$ を $T$ にする方法は何通りか。

• $1 \leq A' \leq N$ かつ $A \neq A'$ であるような整数 $A'$ を選択し、 $A$ を $A'$ に変更する。

ただし、 $N \geq 2$ が成り立っている。

ここで小問題の答えは $N,i$ が同じならば $S,T$ が同じか否かのみに依存することを考えると、以下のようなDPを定義できます。以下、小問題での $N$ は一定とします。
$dp[i'][0]$ $:=$ $i=i',S=1,T=1$ の時の小問題の答え
$dp[i'][1]$ $:=$ $i=i',S=1,T=2$ の時の小問題の答え
$i' = 0$ の時のDPは簡単に構築できます。 $i' \geq 1$ として、最初の操作でどう $A$ を変化させるかを考えると、 $i'$ が $1$ 少ない場合に帰着できます。遷移は以下のようになります。
$dp[i'][0] = dp[i'-1][1] \times (N-1)$
$dp[i'][1] = dp[i'-1][0] + dp[i'-1][1] \times (N-2)$

よって、前準備としてDPテーブルを $i' \leq K$ まで $O(K)$ で完成させておくことで小問題は $O(1)$ で解くことができます。ここで、小問題として解く場合の $N$ は $H,W$ の $2$ 通りのみ考慮すればよいのでDPテーブルを $2$ 回作成し、二項係数の前準備を $O(K)$ で行えば、縦方向の移動を $i$ 回と決め打った時の移動方法は $O(1)$ で求められます。
以上より、この問題は $O(K)$ で解くことができました。

実装例(C++)