Deftly Dodging the Discrete Diagonal

Start at the point \((0, 0)\) on the cartesian plane. At any point, one can move either up one unit, or right one unit. The ultimate destination is the point \((10^6, 10^6)\).

Calculate the number of unique paths there are from the origin to the destination, and answer it modulo \(10^9 + 7\). But, before you do, there's a little catch:

Points of the form \((10^5 n, 10^5 n)\) are off limits for all even \(n\), with the implicit exceptions of \(n \in \{0, 10\}\). Paths that touch any of these points may not be counted towards your total.


  • This problem is not entirely original. It is based on an old Google Code Jam problem. The link will be posted in the solution, so as not to tempt solvers here!
  • Programming skills make this problem easier to solve, but are far from required. Pencil, paper, and Wolfram (or some other similarly featured calculator) are more than sufficient to compute the solution. Pencil and paper alone, however, are most certainly not enough.
  • Yes, \(10^9 + 7\) is prime. This is important.

Image Credit:

Problem Loading...

Note Loading...

Set Loading...