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~.
4 2 3
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~.