Firstly, try to solve a problem only on x-axis.

This means try to implement a function F(x1, x2) that returns Poly, whose k'th coefficient is number of ways to go from x1 to x2 without visiting 0. Here, it would be convenient to assume that we can visit x2 more than one time.

Secondly, let $$$X = F(x_1, x_2)$$$, $$$X' = F(x_2, x_2)$$$, same for $$$Y$$$ and $$$Y'$$$.

Then, divide k'th coefficient of every Poly by $$$k!$$$.

Let $$$A = X \times Y$$$, $$$A' = X' \times Y'$$$

Multiply k'th coefficients of $$$A$$$ and $$$A'$$$ by $$$k!$$$. Now, one can see that $$$A_k = \sum_{i=0}^{k} X_i \times Y_{k-i} \times \binom{k}{i}$$$ =

"from $$$x_1$$$ to $$$x_2$$$ in $$$i$$$ moves" $$$\times$$$ "from $$$y_1$$$ to $$$y_2$$$ in $$$k-i$$$ moves" $$$\times$$$ "choose $$$i$$$ moves from $$$(k-i)+i$$$". Same for $$$A'$$$.

Now, the answer is just $$$A \div A'$$$, because $$$A_k$$$ is the number of ways to go from (x1, y1) to (x2, y2) in k moves, but we can visit (x2, y2) more that once, and $$$A'_k$$$ is the number of ways to go from (x2, y2) to (x2, y2) in k moves.