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

3 2 

2

8 3 

2520