CSES - Counting Sequences | Đếm dãy số
Xem PDF
Điểm:
1700 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Đếm số dãy có độ dài \(n\) mà trong đó mỗi phần tử là một số nguyên từ \(1… k\) và mỗi số nguyên từ \(1… k\) xuất hiện ít nhất một lần trong dãy.
Ví dụ, khi \(n = 6\) và \(k = 4\), một số dãy hợp lệ là \([1,3,1,4,3,2]\) và \([2,2,1,3,4,2]\).
Input
- Một dòng duy nhất chứ 2 số nguyên \(n\) và \(k\).
Output
- Một số nguyên duy nhất: số dãy có thể tạo được sau khi modulo cho \(10^9 + 7\).
Constraints
- \(1\leq k \leq n \leq 10^6\)
Example
Sample Input
6 4
Sample Output
1560
Bình luận
Đếm số dãy có độ dài \(n\) mà trong đó mỗi phần tử là một số nguyên từ \(1, 2, ..., k\) và mỗi số nguyên từ \(1, 2, ..., k\) xuất hiện ít nhất một lần trong dãy.
Ví dụ, khi \(n=6\) và \(k=4\), một số dãy hợp lệ là \([1,3,1,4,3,2]\) và \([2,2,1,3,4,2]\).
Input
Output
Example
Test 1
Input
Output