Bubble Cup V9 E Festival organization

View as PDF

Submit solution

Points: 25
Time limit: 0.6s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

The Prodiggers are quite a cool band and for this reason, they have been the surprise guest at the ENTER festival for the past 80 years. At the beginning of their careers, they weren't so successful, so they had to spend time digging channels to earn money; hence the name.

Anyway, they like to tour a lot and have surprising amounts of energy to do extremely long tours. However, they hate spending two consecutive days without having a concert, so they would very much like to avoid it.

The Prodiggers would like to hold K tours of length of at least L days, and at most R days. Since they are quite superstitious, they want all their tours to have the same length and different schedules (regarding playing concerts and skipping days). Additionally, they would absolutely hate to skip two consecutive days in a single tour. Since their schedule is quite busy, they want you to tell them in how many ways can they hold the K tours, modulo M.

Input Specification

The first and only line of input will contain 3 numbers: K, L, R

Output Specification

Output a single number: in how many ways can they hold the K tours, modulo M=1\,000\,000\,007.

Constraints

  • 1\le K \le 200
  • 1\le L \le R \le 10^{18}

Example Input

1 1 2

Example Output

5

Comments

There are no comments at the moment.