SubsetCheating

Interview

Time limit1sMemory limit1024 MB

Summary

Count the score assignments over N problems where Little Triangle's score is at most Little Square's on each problem, with totals A and B, modulo 1e9+7.

Level: Medium5 of 10
Topics: Math, Combinatorics
Solved: No attempts yet

Problem

Little Square and Little Triangle took a math test. Little Triangle did not study for the test, but Little Square, his best friend, studied well, so Little Triangle was able to copy parts of Little Square's solutions during the test.

The test had $N$ problems in total. On each problem, Little Triangle's score is not more than Little Square's score. All scores are nonnegative integers. We do not know the exact score on any problem, but we know that Little Square has $A$ points in total and Little Triangle has $B$ points in total.

Given $N$ , $A$ , and $B$ , compute the number of ways the two of them could have been scored on the test, modulo $10^9 + 7$ .

Input

The only line of standard input contains three nonnegative integers $N$ , $A$ , and $B$ , separated by a single space, with the meanings explained above.

Output

The standard output contains one integer: the number of ways Little Square and Little Triangle could have been scored on the test, modulo $10^9 + 7$ .

Constraints

$1 ≤ N ≤ 10^6$
$0 ≤ A, B ≤ 10^6$
Two ways of scoring are considered different if Little Square or Little Triangle has a different number of points on at least one of the $N$ problems.

Hint

In the first example, there are $N = 2$ problems. Little Square has $A = 3$ points in total, and Little Triangle has $B = 2$ points in total. Let $P1$ be the first problem and $P2$ the second. There are 6 distinct ways:

Little Square: 0 points on P1, 3 points on P2; Little Triangle: 0 points on P1, 2 points on P2
Little Square: 1 point on P1, 2 points on P2; Little Triangle: 0 points on P1, 2 points on P2
Little Square: 1 point on P1, 2 points on P2; Little Triangle: 1 point on P1, 1 point on P2
Little Square: 2 points on P1, 1 point on P2; Little Triangle: 2 points on P1, 0 points on P2
Little Square: 2 points on P1, 1 point on P2; Little Triangle: 1 point on P1, 1 point on P2
Little Square: 3 points on P1, 0 points on P2; Little Triangle: 2 points on P1, 0 points on P2

Examples4

Example 1
Input
```
2 3 2
```
Expected output
```
6
```
Example 2
Input
```
2 4 6
```
Expected output
```
0
```
Example 3
Input
```
36 43 27
```
Expected output
```
207434534
```
Example 4
Input
```
100001 999999 888888
```
Expected output
```
991579070
```