Explosion-Safe Folding

Time limit1sMemory limit128 MB

Summary

Count ways to fold N tape pieces at seams (straight or 180 degree) so coated faces never touch, given coating patterns from both ends, modulo 10301.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics, Simulation
Solved: No attempts yet

Problem

A tape consists of N equal-length pieces. Each seam between two adjacent pieces may either be left straight or folded by exactly 180 degrees.

One side of every piece is coated with a dangerous volatile substance. On the other side, only some pieces have been coated: the first A pieces from the left and the last B pieces from the right.

After folding, an explosion occurs if two coated faces touch each other. Count the number of folding methods that do not cause an explosion. Leaving every seam straight also counts as one method. Two methods are different if there is at least one seam whose folded-or-straight state differs.

Because the answer can be large, output the number of methods modulo 10301.

Input

The first line contains three natural numbers N, A, and B separated by spaces.

N is the number of pieces. A is the number of leftmost pieces whose other side is also coated, and B is the number of rightmost pieces whose other side is also coated.

The constraints are:

A > 0
B > 0
A + B <= N <= 1000

Output

Print the number of folding methods that do not cause an explosion, modulo 10301.

Examples3

Example 1
Input
```
4 1 1
```
Expected output
```
6
```
Example 2
Input
```
5 2 2
```
Expected output
```
1
```
Example 3
Input
```
6 1 2
```
Expected output
```
7
```