Số được coi là đặc biệt nếu như số đó có thể phân tích thành tổng các lũy thừa cơ số ~k~ riêng biệt,

Ví dụ: ~10~ là số đặc biệt cơ số ~3~ vì ~10 = 3^2 + 3^0~,

Yêu cầu: Tìm số đặc biệt nhỏ nhất lớn hơn hoặc bằng ~N~.

Input

• Gồm ~1~ dòng duy nhất ghi ~2~ số nguyên dương ~N (0 \le N \le 10^7)~ và ~k (2 \le k \le 10^7)~.

Output

• Ghi ~1~ số nguyên dương duy nhất là kết quả của bài toán trên sau khi chia dư cho ~10^9 + 7~.

Sample

Input #1

8 3

Output #1

9

Input #2

17 4

Output #2

17

Hint

Giải thích #2:

• ~17~ là số nhỏ nhất thõa mãn: ~N \le 17~ và ~17 = 4^0 + 4^2~