Deftly Dodging the Discrete Diagonal

We'll set $P = 10^9 + 7$ for brevity.

---

Let $f(d)$ be the number of different paths from any point $(x, y)$ to another point $(x+d, y+d)$ , ignoring the forbidden points for now. Since the total number of moves that need to be made is $2d$ , and exactly $d$ of them need to be rightward moves, we have:

$f(d) = \binom{2d}{d}$

It's important to note that we can compute $f(d)$ in limited space modulo $P$ - something which Wolfram will automagically do for you, but that you'll have to implement yourself if using a lesser calculator. This can be accomplished via three observations:

• $\binom{n}{k}\:\text{mod}\:P \equiv \frac{n!}{k! \cdot (n-k)!}\:\text{mod}\:P \equiv n! \cdot (k! \cdot (n-k)!)^{-1}\:\text{mod}\:P$

• $x^{-1}\:\text{mod}\:P \equiv x^{P-2} \mod P$ Euler's Theorem

• $a^b\:\text{mod}\:P$ can be computed in $O(\log_2 b)$ steps, using exponentiation by squaring

These three things let us compute $f(d)\:\text{mod}\:P$ relatively quickly.

---

Now, we need to account for the forbidden points. We can do this through a simple application of the inclusion-exclusion principle .

More succinctly, let's define $g(n)$ to be the number of ways to get from $(0, 0)$ to $(2n \cdot 10^5, 2n \cdot 10^5)$ , without hitting any forbidden points in between (we ignore the fact that the destination might be a forbidden point for this calculation), and let $h(n)$ be the same as $g(n)$ , except ignoring the forbidden point restriction entirety. Considering all unique-to-order ways there are to sum to $5$ , the inclusion-exclusion principle gives us:

$h(n) = f(2 \cdot 10^5 \cdot n)$

$g(5) = h(5) - 2h(4)h(1) - 2h(3)h(2) + 3h(3)h^2(1) + 3h^2(2)h(1) - 4h(2)h^3(1) + h^5(1)$

We can use a calculator to get $h(n)\:\text{mod}\:P$ for all necessary $n$ . Then, we can plug into the above formula, and arrive at the answer:

$g(5) \equiv 530023407\:\text{mod}\:P$

---

The inspiration for this problem can be found here . It is quite a bit more difficult than this one, and requires some strong programming skills to solve!