Stationary bike programs

Time limit1sMemory limit1024 MB

Summary

Count sequences of T levels where each step changes by exactly 1 and all values stay between M and N, modulo 1e9+7.

Level: Medium6 of 10
Topics: Dynamic programming
Solved: No attempts yet

Problem

Vinícius likes working out at the gym. He agreed with his trainer to get a different exercise program every time he uses the stationary bike. In gym language, a program is a sequence of exercise difficulty levels listed in time order. All of Vinícius's stationary bike programs must last the same number of minutes, and the difficulty must change every minute to the level immediately above or the level immediately below. A difficulty level may never fall below a fixed minimum or rise above a fixed maximum.

In other words, a program of $T$ minutes is a sequence of $T$ integers, one difficulty level per minute, where two neighbouring minutes differ by exactly $1$ . Count the different programs the trainer can build under these rules.

Input

The input consists of a single line with three integers $T$ , $M$ , and $N$ ( $1 \le T \le 50$ , $1 \le M < N \le 100000$ ).

$T$ is the number of minutes of the exercise, $M$ is the smallest allowed difficulty level, and $N$ is the largest allowed difficulty level.

Output

Print a single line with the number of different programs the trainer can build. This number can be very large, so print it modulo $10^9 + 7$ .

Examples3

Example 1
Input
```
3 2 5
```
Expected output
```
10
```
Example 2
Input
```
30 2 5
```
Expected output
```
4356618
```
Example 3
Input
```
50 1 100000
```
Expected output
```
738072143
```