Comet OJ

C1724 [CEOI2016Day1] Kangaroo

内存限制：256 MB 时间限制：1000 ms

题目描述

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 numberedcs. Then he jumps from cell to cell, eating the plants as he goes. He will always finish in cell numberedcf, after visiting each of the $N$ cells exactly once, includingcsandcf. 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 numberedcurrentafter he jumped there from a cell numberedprev, and will jump fromcurrentto cell numberednext, then:

  • ifprev < current, thennext < current;else,
  • ifcurrent < prev, thencurrent < next.

Knowing the number $N$ of cells in the garden, the starting cellcsfrom where the kangaroo starts to eat plants and the final cellcfwhere 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$, $cs$, $cf$.

输出

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

样例

样例输入 1

4 2 3

样例输出 1

2

提示

Notes and constraints

  • $2 ≤ N ≤ 2000$
  • $1 ≤ cs ≤ N$
  • $1 ≤ cf ≤ N$
  • $cs ≠ cf$
  • For tests worth 6 points, $N ≤ 8$.
  • For tests worth 36 points, $N ≤ 40$.
  • For tests worth 51 points, $N ≤ 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 cs.