Hide

Problem H
Kaboom

Luka found an interesting tape in the chem lab. The tape is divided into $N$ segments of equal length, and can easily be bent between two segments, but only by exactly $180$ degrees.

One side of the tape is completely covered with a very volatile chemical. If the chemical comes in contact with itself, it reaches critical mass and explodes.

The other side of the tape is not completely covered yet. Only the first $A$ segments and last $B$ segments are covered, with the exact same chemical.

Write a program that will calculate the number of different ways Luka can bend the tape so that it does not explode. He can bend the tape more than once and two ways are different if there is at least one bevel between segments that is not bent in one and is bent in the other

Since the solution can be huge, print the result modulo $10\, 301$.

The example in Figure 1 illustrates all $6$ possible ways for $N=4$, $A=1$ and $B=1$. For clarity, the tape is only bent $90$ degrees on the illustration. Luka would actually bend it $180$ degrees.

\includegraphics[width=6cm]{meh-012.png}
\includegraphics[width=4.5cm]{meh-013.png}
\includegraphics[width=4.5cm]{meh-014.png}
\includegraphics[width=3cm]{meh-015.png}
\includegraphics[width=3cm]{meh-016.png}
\includegraphics[width=3cm]{meh-017.png}
Figure 1: Ways to bend a tape of length $4$ with $1$ left and $1$ right segments covered

Input

The first and only line of input contains three natural numbers $N$, $A$ and $B$ ($A>0$, $B>0$, $A+B \leq N \leq 1\, 000$), total number of segments, number of covered segments from the left and from the right respectively.

Output

The first and only line of output should contain the number of possible ways to bend the tape modulo $10\, 301$.

Sample Input 1 Sample Output 1
4 1 1
6
Sample Input 2 Sample Output 2
5 2 2
1
Sample Input 3 Sample Output 3
6 1 2
7

Please log in to submit a solution to this problem

Log in