Link đề bài : http://vnoi.info/problems/show/BASEH/.

Đề bài :

Cho một dãy số a[1],a[2],a[3],…,a[n] và hai số K,H được xác định như sau:

• a[1]=1.
• Nếu K chẵn thì a[K] = H * a[K / 2].
• Nếu K lẻ thì a[K] = H * a[(K - 1) / 2] + 1.

Các bạn hãy lập trình tính số thứ K của dãy viết trong hệ cơ số H.

Input

• Gồm một dòng duy nhất chứa 2 số K,H.

Output

• In ra số duy nhất là kết quả bài toán.

Giới hạn

• 0< K <=1000000000.
• 0=< H <=2008.

Ví dụ

Input
7 110

Output
111

Soluntion :

Here

Code :

Here