CEOI '16 P2 - Kangaroo

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 512M

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

A garden is composed of a row of N cells numbered from 1 to N. Initially, all cells contain plants. A kangaroo arrived in the garden in cell numbered c_s. Then he jumps from cell to cell, eating the plants as he goes. He will always finish in cell numbered c_f, after visiting each of the N cells exactly once, including c_s and c_f. Obviously, the kangaroo will make N-1 jumps.

The kangaroo doesn't want to be caught, so after each jump he changes the direction in which he jumps next: if he is currently in cell numbered current after he jumped there from a cell numbered prev, and will jump from current to cell numbered next, then:

  • if prev < current, then next < current ; else,
  • if current < prev, then current < next.

Knowing the number N of cells in the garden, the starting cell c_s from where the kangaroo starts to eat plants and the final cell c_f where the kangaroo finishes, you should calculate the number of distinct routes the kangaroo can take while jumping through the garden.


The input will contain three space separated positive integers N, c_s, c_f.


In the output, you should write a single integer, the number of distinct routes the kangaroo can take modulo 1\,000\,000\,007 (10^9 + 7).

Notes and constraints

  • 2 \le N \le 2\,000
  • 1 \le c_s \le N
  • 1 \le c_f \le N
  • c_s \ne c_f
  • For tests worth 6 points, N \le 8.
  • For tests worth 36 points, N \le 40.
  • For tests worth 51 points, N \le 200.
  • Any route is uniquely determined by the order in which cells are visited.
  • We guarantee that for each test there is at least one route which follow the rules.
  • The kangaroo can start jumping in any direction from c_s.

Sample Input

4 2 3

Sample Output



The kangaroo starts from cell 2 and finishes in cell 3. The two correct routes are 2 \to 1 \to 4 \to 3 and 2 \to 4 \to 1 \to 3.


There are no comments at the moment.