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\)\(k = 4\), một số dãy hợp lệ là \([1,3,1,4,3,2]\)\([2,2,1,3,4,2]\).

Input

  • Một dòng duy nhất chứ 2 số nguyên \(n\)\(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


  • 0
    Thanh72    3:19 p.m. 19 Tháng 8, 2023 đã chỉnh sửa

    Đế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\)\(k=4\), một số dãy hợp lệ là \([1,3,1,4,3,2]\)\([2,2,1,3,4,2]\).

    Input

    • Một dòng duy nhất chứa \(2\) số nguyên \(n\)\(k\) \((1 \leq k \leq n \leq 10^6)\).

    Output

    • In ra số dãy có thể tạo được modulo cho \(10^9+7\).

    Example

    Test 1

    Input
    6 4
    Output
    1560