Cho hai số nguyên dương \(n, k\). Đếm xem có bao nhiêu hoán vị \(p_1, p_2, ..., p_n\) của \(1, 2, ..., 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 > \frac{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

Test 2

Input

        8 3

Output

        2520

Giải thích

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