Hopscotch

Time limit2sMemory limit512 MB

Summary

Count lattice paths from (0,0) to (N,N) where each hop increases x by at least X and y by at least Y, modulo 1e9+7.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics, Math, Prefix sum
Solved: No attempts yet

Problem

You are playing hopscotch. You start at the origin and your goal is to hop to the lattice point $(N, N)$ . A hop takes you from a lattice point $(x_1, y_1)$ to a lattice point $(x_2, y_2)$ with $x_1 < x_2$ and $y_1 < y_2$ .

You dislike short hops. So you have decided that on every hop between two lattice points, the $x$ -coordinate must increase by at least $X$ and the $y$ -coordinate must increase by at least $Y$ .

Count the distinct paths from $(0, 0)$ to $(N, N)$ that respect these constraints. Two paths are distinct if there is some lattice point that you visit on one path and not on the other.

Hint: the answer is taken modulo $10^9 + 7$ . If $p$ is a prime such as $10^9 + 7$ and $x$ is an integer that is not $0$ modulo $p$ , then $x \cdot x^{p-2} \equiv 1 \pmod p$ .

Input

The first line holds three integers $N$ , $X$ , $Y$ separated by single spaces. You may assume $1 \le X, Y \le N \le 10^6$ .

Output

The number of distinct paths can be very large. Print that number modulo $1\,000\,000\,007$ ( $10^9 + 7$ ) on one line.

Examples5

Example 1
Input
```
2 1 1
```
Expected output
```
2
```
Example 2
Input
```
7 2 3
```
Expected output
```
9
```
Example 3
Input
```
1 1 1
```
Expected output
```
1
```
Example 4
Input
```
5 5 5
```
Expected output
```
1
```
Example 5
Input
```
10 1 1
```
Expected output
```
48620
```