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