Problem H

You’re playing hopscotch! You start at the origin and your goal is to hop to the lattice point $(N, N)$. A hop consists of going from lattice point $(x_1, y_1)$ to $(x_2, y_2)$, where $x_1 < x_2$ and $y_1 < y_2$.

You dislike making small hops though. You’ve decided that for every hop you make between two lattice points, the x-coordinate must increase by at least $X$ and the y-coordinate must increase by at least $Y$.

Compute the number of distinct paths you can take between $(0, 0)$ and $(N, N)$ that respect the above constraints. Two paths are distinct if there is some lattice point that you visit in one path which you don’t visit in the other.

Hint: The output involves arithmetic mod $10^9+7$. Note that with $p$ a prime like $10^9+7$, and $x$ an integer not equal to $0$ mod $p$, then $x(x^{p-2})$ mod $p$ equals $1$ mod $p$.


The input consists of a line of three integers, $N$ $X$ $Y$. You may assume $1 \le X, Y \le N \le 10^{6}$.


The number of distinct paths you can take between the two lattice points can be very large. Hence output this number modulo 1 000 000 007 ($10^9 + 7$).

Sample Input 1 Sample Output 1
2 1 1
Sample Input 2 Sample Output 2
7 2 3
CPU Time limit 7 seconds
Memory limit 1024 MB
Source 2017 ICPC Mid-Central Regional
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in