Đếm hoán vị

Xem PDF

Điểm: 600 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho hai số nguyên dương \(n, k\). Đếm xem có bao nhiêu hoán vị \(p_{1}, p_{2}, \ldots, p_{n}\) của \(1, 2, \ldots, n\) thỏa mãn \(p_{i} > p_{i / k}\) với mọi \(1 \leq i \leq n\).

Trong đó, \(a / b\) là số nguyên lớn nhất không vượt quá \(\dfrac{a}{b}\) và quy ước \(p_{0} = 0\).

Input

  • Gồm hai số nguyên dương \(n, k\) \((1 \leq n, k \leq 10^{6})\).

Output

  • In ra số lượng hoán vị thỏa mãn điều kiện sau khi \(\mod (10^{9} + 7)\).

Scoring

  • Subtask \(1\) (\(20\%\) số điểm): \(n \leq 10\).
  • Subtask \(2\) (\(10\%\) số điểm): \(k > n\).
  • Subtask \(3\) (\(10\%\) số điểm): \(k = n\).
  • Subtask \(4\) (\(20\%\) số điểm): \(k > \dfrac{n}{2}\).
  • Subtask \(5\) (\(20\%\) số điểm): \(n, k \leq 10^{3}\).
  • Subtask \(6\) (\(20\%\) số điểm): \(n, k \leq 10^{6}\).

Example

Test 1

Input
3 2 
Output
2
Note

Trong test 1, chúng ta cần tìm các hoán vị thỏa mãn \(p_{3} > p_{1}\)\(p_{2} > p_{1}\). Có 2 hoán vị như vậy \((1, 2, 3)\)\((1, 3, 2)\).

Test 2

Input
8 3 
Output
2520

Bình luận


  • -1
    mbfibat 6:36 p.m. 1 Tháng 6, 2020 đã chỉnh sửa

    Bài này hay phết :v