캥거루

시간 제한2초메모리 제한512 MB

요약

한 줄로 놓인 N개의 칸을 캥거루가 cs에서 출발해 cf에서 멈추며 모두 정확히 한 번씩 방문할 때, 매 점프마다 방향을 바꾸는 경로의 수를 세는 문제이다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 조합론
정답자: 아직 제출이 없습니다

문제

정원은 1번부터 $N$ 번까지 번호가 붙은 칸이 한 줄로 늘어선 모양이다. 처음에는 모든 칸에 식물이 있다.

캥거루는 $c_s$ 번 칸에 내려앉아 그 칸의 식물을 먹는다. 그다음부터는 칸에서 칸으로 뛰어다니며 내려앉은 칸의 식물을 먹고, $N$ 개의 칸을 모두 정확히 한 번씩 방문한 뒤 $c_f$ 번 칸에서 멈춘다. 출발한 칸과 마지막 칸도 방문한 칸에 들어가므로 캥거루는 정확히 $N-1$ 번 뛴다.

캥거루는 잡히지 않으려고 한 번 뛸 때마다 다음에 뛸 방향을 바꾼다. $prev$ 번 칸에서 $current$ 번 칸으로 뛴 다음 $current$ 번 칸에서 $next$ 번 칸으로 뛴다면 아래 두 조건이 성립한다.

$prev < current$ 이면 $next < current$ 이다.
$current < prev$ 이면 $current < next$ 이다.

칸의 수 $N$ 과 출발 칸 $c_s$ , 마지막 칸 $c_f$ 가 주어질 때 캥거루가 지나갈 수 있는 서로 다른 경로의 수를 구하라.

입력

첫째 줄에 양의 정수 $N$ , $c_s$ , $c_f$ 가 공백으로 구분되어 주어진다.

$2 \le N \le 2000$
$1 \le c_s \le N$
$1 \le c_f \le N$
$c_s \ne c_f$
경로는 칸을 방문하는 순서로 구분한다.
규칙을 만족하는 경로가 적어도 하나 있는 입력만 주어진다.
캥거루는 $c_s$ 번 칸에서 어느 방향으로든 처음 뛸 수 있다.

출력

규칙을 만족하는 서로 다른 경로의 수를 $1000000007$ ( $10^9 + 7$ )로 나눈 나머지를 한 줄에 출력한다.

힌트

첫 번째 예제에서 캥거루는 2번 칸에서 출발해 3번 칸에서 멈춘다. 규칙을 만족하는 경로는 2 → 1 → 4 → 3과 2 → 4 → 1 → 3, 두 가지다.

예제2

예제 1
입력
```
4 2 3
```
예상 출력
```
2
```
예제 2
입력
```
2 1 2
```
예상 출력
```
1
```