Số đặc biệt - LCOJ: Luyen Code Online

SPNUM - Số đặc biệt

Điểm: 1,00 (OI)

Giới hạn thời gian: 0.005s

Giới hạn bộ nhớ: 256M

Tác giả:

siro

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

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

Input #2

17 4

Output #2

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~

Bình luận

Hãy đọc nội quy trước khi bình luận.

  ll key(ll n,ll k,ll z, ll i)
  {   if(n==0) return z;
if(n%k<=1)
{
    return key((n-n%k)/k,k,z,i*k);
}
else 
{
    return key((n+k-n%k)/k,k,z+(k-n%k)*i,i*k);
}
  }
 void solve()
  {
 ll n,k;cin>>n>>k;
cout<<(n+key(n,k,0,1))%MOD;
  }