시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 512 MB 154 30 (19%) 29
문제
태양이네 별장 앞마당에 있는 정원은 N개의 칸이 일렬로 나열된 모양이다. 왼쪽부터 차례대로 각 칸에 1부터 N 사이의 번호를 매긴다. 처음에 정원의 각 칸에 풀들이 풍성하게 있다. 명우는 태양이네 정원에 자신의 애완용 캥거루를 풀어놓았다. 초기 캥거루의 위치는 cs번 칸이다. 캥거루는 각 칸 사이를 점프해가며 정원의 모든 칸을 방문하여 풀들을 모조리 먹어치우고 cf번 칸에서 명우와 만나기로 했다. 캥거루는 칸에 방문할 때 칸에 있는 모든 풀들을 먹어치우기 때문에 한 번 방문했던 칸에 다시 방문하지는 않는다. 그래서 cs번 칸과 cf번 칸을 포함해서 모든 칸을 한 번씩 방문하고, 이 때 총 N-1번의 점프를 하게 된다. 명우의 캥거루는 고도로 훈련되어 있어 중간에 태양이에게 잡히지 않도록 왼쪽 오른쪽으로 번갈아 가면서 뛴다. 즉, 현재 있는 칸의 번호가 current, 이전에 있던 칸 번호가 prev, 다음에 이동할 칸 번호가 next 라고 할 때, 아래 규칙에 따라 점프한다: * 만약 prev < current라면, next < current이다. * 만약 current < prev라면, current < next이다. 정원에 있는 칸의 개수 N과 캥거루의 시작 위치 cs, 캥거루의 종료 위치 cf가 주어졌을 때 캥거루가 이동하는 서로 다른 경로의 수를 구하자. 경로가 서로 다르다는 것은 방문한 칸의 번호를 나열했을 때 다르다는 것이고, 처음에 캥거루가 뛰는 방향은 두 방향 모두 가능하다.
입력
첫 줄에 정원에 있는 칸의 수 N과 캥거루의 시작 위치 cs, 캥거루의 종료 위치 cf가 공백으로 구분되어 주어진다. (2 ≤ N ≤ 2,000, 1 ≤ cs, cf ≤ N, cs ≠ cf) 6점에 해당하는 서브태스크는 N ≤ 8 이고, 36점에 해당하는 서브태스크는 N ≤ 40 이고, 51점에 해당하는 서브태스크는 N ≤ 200 이다.
출력
첫 줄에 캥거루의 서로 다른 이동 경로의 수를 출력한다. 단, 답이 매우 클 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.
힌트
#### 입력 예제 ``` 4 2 3 ``` #### 출력 예제 ``` 2 ``` #### 예제 설명 캥거루는 2번 칸에서 시작해서 3번 칸에서 종료한다. 이 때 두 경로는 2 -> 1 -> 4 -> 3과 2 -> 4 -> 1 -> 3이 된다.