Bessie biết một số \(x+0.5\), trong đó \(x\) là một số nguyên từ \(0\) đến \(N\), kể cả hai đầu mút (\(1 \le N \le 5000\)).

Elsie đang cố đoán số này. Cô có thể đặt câu hỏi "số \(i\) cao hay thấp?" với một số nguyên \(i\) từ \(1\) đến \(N\), kể cả hai đầu mút. Bessie trả lời "HI!" nếu \(i\) lớn hơn \(x+0.5\), hoặc "LO!" nếu \(i\) nhỏ hơn \(x+0.5\).

Elsie nghĩ ra chiến lược sau để đoán số của Bessie. Trước khi đưa ra bất kỳ dự đoán nào, cô lập một danh sách gồm \(N\) số, trong đó mỗi số từ \(1\) đến \(N\) xuất hiện đúng một lần (nói cách khác, danh sách là một hoán vị có kích thước \(N\)). Sau đó, cô lần lượt duyệt danh sách và đoán các số theo thứ tự xuất hiện. Tuy nhiên, Elsie bỏ qua mọi dự đoán không cần thiết. Cụ thể, nếu Elsie sắp đoán số \(i\) và trước đó đã đoán một số \(j<i\) mà Bessie trả lời "HI!", Elsie sẽ không đoán \(i\) và chuyển sang số tiếp theo trong danh sách. Tương tự, nếu Elsie sắp đoán số \(i\) và trước đó đã đoán một số \(j>i\) mà Bessie trả lời "LO!", Elsie sẽ không đoán \(i\) và chuyển sang số tiếp theo trong danh sách. Có thể chứng minh rằng với chiến lược này, Elsie luôn xác định duy nhất được \(x\), bất kể cô lập hoán vị nào.

Nếu nối tất cả câu trả lời "HI" hoặc "LO" của Bessie thành một xâu duy nhất \(S\), số lần Bessie nói "HILO" được định nghĩa là số xâu con độ dài \(4\) của \(S\) bằng "HILO".

Bessie biết Elsie sẽ sử dụng chiến lược này và đã chọn giá trị của \(x\), nhưng cô không biết Elsie sẽ dùng hoán vị nào. Hãy tính tổng số lần Bessie nói "HILO" trên tất cả các hoán vị mà Elsie có thể chọn, lấy modulo \(10^9+7\).

Dữ liệu vào

Dòng duy nhất chứa \(N\) và \(x\).

Dữ liệu ra

In ra tổng số lần xuất hiện của "HILO", lấy modulo \(10^9+7\).

Phân nhóm

• Các test 3–10 thỏa mãn \(N \le 50\).
• Các test 11–18 thỏa mãn \(N \le 500\).
• Các test 19–26 không có ràng buộc bổ sung.

Ví dụ

4 2

17

60 10

508859913

Nguồn

USACO 2021 December Contest, Platinum — HILO. Tác giả: Richard Qi.

https://usaco.org/index.php?page=viewproblem2&cpid=1166