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