Mã bài:
kinv
Điểm:
4 (OI)
Giới hạn thời gian:
10.0s
Giới hạn bộ nhớ:
512M
Dữ liệu vào:
stdin
Dữ liệu ra:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Golang, Java, Pascal, Perl, Python, Rust
Gọi ~f(P)~ là số lượng cặp nghịch thế của một hoán vị ~P~. Cho hai số nguyên ~n~ và ~k~, hãy đếm số lượng hoán vị ~P~ của dãy ~\{1, 2, \dots, n\}~ sao cho ~f(P) = k~. Do đáp án có thể khá lớn, hãy in phần dư của đáp án khi chia cho ~10^9+7~.
Input
Gồm một dòng dyu nhất ghi hai số nguyên ~n~ và ~k~.
Output
In ra số hoán vị của dãy ~\{1, 2, \dots, n\}~ có ~k~ cặp nghịch thế, theo modulo ~10^9+7~.
Giới hạn
- Subtask 1 ~(30\%)~: ~1 \leq n \leq 300, 0 \leq k\leq \min\{C_n^2, 300\}~
- Subtask 2 ~(30\%)~: ~1 \leq n \leq 3000, 0 \leq k\leq \min\{C_n^2, 3000\}~.
- Subtask 3 ~(40\%)~: ~1 \leq n \leq 10^5, 0 \leq k\leq \min\{C_n^2, 10^5\} ~.
Sample Input
3 2
Sample Output
2
Giải thích
Các hoán vị của dãy ~\{1, 2, 3\}~ có ~2~ cặp nghịch thế là
- ~\{3, 1, 2\}~
- ~\{2, 3, 1\}~
Như vậy đáp án cho test ví dụ là ~2~.
Bình luận