Simulare🎅🏼🎄 | SubsetCheating

Task

Little Square and Little Triangle took a math test. Little Triangle didn’t study for the test, but, fortunately for him, Little Square, his best friend, succeeded in studying for the exam, so Little Triangle was able to copy parts of Little Square’s solutions on the test.

We know that the test had $N$ problems in total and that at each one of them Little Triangle’s score is not more than Little Square’s score. All scores are nonegative integers. We don’t know the exact score of any of them at any problem, but we know that in total Little Square has $A$ points while Little Triangle has $B$ points total.

Knowing $N$ (the number of problems that made up the math test), $A$ (the sum of the scores that Little Square got on the problems) and $B$ (Little Triangle’s sum of scores), we want to compute the number of ways in which the two of them could have been scored on the test, modulo $10^9 + 7$.

Input data

The sole line of the input file subset.in will contain tree nonnegative integers $N$, $A$ and B, separated by a single space, with the same meaning as explained above.

Output data

The output file subset.out will contain only one integer, representing the number of ways in which Little Square and Little Triangle could have been scored on the test, modulo $10^9 + 7$.

Constraints

• $1 \leq N \leq 10^6$
• $0 \leq A, B \leq 10^6$
• $2$ ways of scoring are considered distinct (different) if Little Square or Little Triangle have a different number of points on at least one of the $N$ problems.

Example 1

subset.in

2 3 2

subset.out

6

Explanation

In the first example, we have $N = 2$ problems on the math test. Little Square has $A = 3$ points in total, while Little Triangle has $B = 2$ points in total. From now on let $P1$ be the first problem, and $P2$ the second problem.

There are $6$ distinct ways in which Little Square and Little Triangle could have scored on the test:

• Little Square: $0$ points - $P1$, $3$ points - $P2$; Little Triangle: $0$ points - $P1$, $2$ points - $P2$
• Little Square: $1$ points - $P1$, $2$ points - $P2$; Little Triangle: $0$ points - $P1$, $2$ points - $P2$
• Little Square: $1$ points - $P1$, $2$ points - $P2$; Little Triangle: $1$ points - $P1$, $1$ points - $P2$
• Little Square: $2$ points - $P1$, $1$ points - $P2$; Little Triangle: $2$ points - $P1$, $0$ points - $P2$
• Little Square: $2$ points - $P1$, $1$ points - $P2$; Little Triangle: $1$ points - $P1$, $1$ points - $P2$
• Little Square: $3$ points - $P1$, $0$ points - $P2$; Little Triangle: $2$ points - $P1$, $0$ points - $P2$

Example 2

subset.in

2 4 6

subset.out

0

Example 3

subset.in

36 43 27

subset.out

207434534

Example 4

subset.in

100001 999999 888888

subset.out

991579070