CEOI '16 P2 - Kangaroo

View as PDF

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 cells numbered from to . Initially, all cells contain plants. A kangaroo arrived in the garden in cell numbered . Then he jumps from cell to cell, eating the plants as he goes. He will always finish in cell numbered , after visiting each of the cells exactly once, including and . Obviously, the kangaroo will make 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 after he jumped there from a cell numbered , and will jump from to cell numbered , then:

• if , then ; else,
• if , then .

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

Input

The input will contain three space separated positive integers .

Output

In the output, you should write a single integer, the number of distinct routes the kangaroo can take modulo .

Notes and constraints

• For tests worth points, .
• For tests worth points, .
• For tests worth points, .
• 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 .

Sample Input

4 2 3

Sample Output

2

Explanation

The kangaroo starts from cell and finishes in cell . The two correct routes are and .