Vinh đang tích cực chuẩn bị để tham gia vào kỳ thi Olympic Tin học Sinh viên Việt Nam, khối Siêu cúp. Khi xem lại đề thi của những kỳ thi gần đây, Vinh nhận thấy còn chưa có nhiều bài có liên quan đến việc áp dụng tìm kiếm nhị phân. Là người có nhiều kinh nghiệm từ các kỳ thi học sinh giỏi, Vinh nhanh chóng viết được đoạn mã cài đặt tìm kiếm nhị phân bằng ngôn ngữ C++ như sau:
int binary_search(vector<int> &a, int key) {
int l = 0, r = (int)a.size() - 1;
while (l <= r) {
int mid = (l + r + 1) / 2;
if (a[mid] == key) return mid;
if (a[mid] > key) r = mid - 1;
else l = mid + 1;
}
return -1;
}
Trong khi thực hiện kiểm thử chương trình, Vinh nhận thấy rằng dãy số đầu vào chưa được sắp xếp. Rất may vấn đề được phát hiện sớm và kịp thời xử lý. Tuy nhiên, trong đầu Vinh nảy ra một câu hỏi thú vị: "Có bao nhiêu hoán vị của các số nguyên từ ~1~ đến ~n~ mà hàm binary_search trả lại đúng chỉ số ~i~ sao cho ~a[i]=key~".
Hãy giúp Vinh giải quyết bài toán này. Vì đáp án có thể rất lớn, chỉ cần tìm số dư khi chia cho ~10^9+7~.
Input
Một dòng duy nhất gồm hai số nguyên ~n~ và ~key~ (~1\le key\le n\le 100000~) — độ dài và giá trị cần tìm đúng trong các hoán vị.
Output
Một số nguyên là đáp án của bài toán modulo ~10^9+7~.
Scoring
Subtask | Điểm | Giới hạn |
---|---|---|
1 | ~10~ | ~n \le 20~ |
2 | ~20~ | ~n \le 200~ |
3 | ~30~ | ~n\le 30000~ |
4 | ~40~ | Không có giới hạn gì thêm |
Sample Input 1
3 1
Sample Output 1
4
Sample Input 2
1 1
Sample Output 2
1
Bình luận