Một khu vườn được biểu diễn dưới dạng một hàng ngang gồm \(N\) ô đánh số từ \(1\) đến \(N\). Ban đầu, tất cả các ô đều có chứa trái cây. Một con kangaroo chạy tới khu vườn từ ô \(\text{cs}\). Sau đó nó bắt đầu nhảy đến từng ô trong vườn để ăn hết trái cây ở các ô đó. Nó sẽ luôn kết thúc lộ trình ăn uống của mình ở ô \(\text{cf}\), sau khi nhảy qua đúng \(N\) ô khác nhau, mỗi ô được nhảy vào đúng một lần, bao gồm cả ô \(\text{cs}\) và ô \(\text{cf}\). Hiển nhiên, con kangaroo này sẽ nhảy tổng cộng \(N-1\) bước.
Vì con kangaroo không muốn bị bắt nên sau mỗi bước nhảy nó đều sẽ đổi hướng nhảy so với lần nhảy trước: Nếu nó đang đứng ở ô \(\text{current}\) sau khi nhảy đến từ ô \(\text{prev}\), và từ ô này nó sẽ tiếp tục nhảy đến ô \(\text{next}\), thì những điều kiện sau bắt buộc phải được thỏa mãn:
- Nếu \(\text{prev} < \text{current}\) thì \(\text{next} < \text{current}\);
- Nếu \(\text{current} < \text{prev}\) thì \(\text{current} < \text{next}\).
Cho trước \(N\) là số lượng ô trong vườn, \(\text{cs}\) là ô xuất phát của kangaroo và \(\text{cf}\) là ô cuối cùng mà nó nhảy tới, bạn hãy tính số lượng lộ trình phân biệt mà con kangaroo này có thể nhảy được trong khu vườn.
Input
Gồm một dòng duy nhất chứa ba số nguyên \(N\), \(\text{cs}\) và \(\text{cf}\).
Output
Ghi ra một số nguyên duy nhất là phần dư sau khi chia số lộ trình phân biệt cho \(10^9+7\).
Ví dụ
Input
4 2 3
Output
2
Giải thích
Con kangaroo xuất phát ở ô \(2\) và kết thúc ở ô \(3\). Hai lộ trình mà nó có thể nhảy qua là \(2\rightarrow 1\rightarrow 4\rightarrow 3\) và \(2\rightarrow 4\rightarrow 1\rightarrow 3\).
Ràng buộc
- \(2\leq N\leq 2000\).
- \(1\leq \text{cs}\leq N\).
- \(1\leq \text{cf}\leq N\).
- \(\text{cs}\neq\text{cf}\).
- Các lộ trình được xác định bằng thứ tự các ô mà con kangaroo nhảy đến.
- Dữ liệu đảm bảo tồn tại ít nhất một lộ trình thỏa mãn các ràng buộc.
- Con kangaroo có thể nhảy theo bất kỳ hướng nào khi nó xuất phát ở ô \(\text{cs}\).
- \(6\%\) số test có \(N\leq 8\).
- \(36\%\) số test có \(N\leq 40\).
- \(51\%\) số test có \(N\leq 200\).