Gymnastics
By Maratona de Programação da SBC 2017 
Brazil
By Maratona de Programação da SBC 2017 Brazil
Vinícius really enjoys exercising in the gym. He made an agreement with his trainer to have different exercise programs every time he uses the exercise bike. A program, in gym lingo, is a sequence of exercise difficulty levels. Vinicius' programs for the exercise bike must have the same duration in minutes and the difficulty levels must change every minute, to a level just above or a level just below. The levels of difficulty cannot be below a pre-established minimum or above a pre-established maximum.
Your challenge is to calculate the number of different programs that the trainer can build, given the above constraints.
The input consists of a single line containing three integers, T, M, N (1 ≤ T ≤ 50 , 1 ≤ M < N ≤ 105) where T is the number of minutes of the exercise, M is the minimum allowed difficulty value, and N is the maximum allowed difficulty value.
Your program has to produce a single line with an integer representing the number of different programs that the trainer can build. Since this number can be large, the answer should be this number modulo 109 + 7.
| Input Sample | Output Sample |
|
3 2 5 |
10 |
|
30 2 5 |
4356618 |
|
50 1 100000 |
738072143 |