Số $0$ có nghĩa

Trong giờ học Tin học lớp \(10\), nội dung đổi số từ hệ thập phân về số ở hệ nhị phân làm An rất thích thú. Hệ nhị phân là hệ số mà các máy tính sử dụng để lưu trữ dữ liệu và tính toán. An thấy nếu số \(0\) đặt trước các số đều vô nghĩa, việc này giống như các số \(0\) ở đầu các số ở hệ thập phân. Sau khi làm một số bài tập đổi hệ cơ số, An thường hay đếm số lượng số \(0\) sau khi biểu diễn ở hệ nhị phân.

Hôm nay An đưa ra hai số tự nhiên \(N, K\) (\(0 \le N \le 10^{18}\), \(0 \le K \le 10^2\)) và nhờ Bình cho biết có bao nhiêu số thập phân khác nhau từ \(1\) tới \(N\) mà khi biểu diễn ở hệ nhị phân có đúng \(K\) chữ số \(0\) có nghĩa (không tính các chữ số \(0\) đứng đầu).

Yêu cầu: Hãy giúp Bình trả lời câu hỏi của An.

Input

Dữ liệu vào:hai số \(N, K\) trên một dòng.

Ràng buộc:

• Có \(40\%\) số test tương ứng \(40\%\) số điểm với \(1 < N \le 10^6\);

• Có \(30\%\) số test tương ứng \(30\%\) số điểm với số \(N\) có dạng \(2^M\) (\(M\) là số tự nhiên và \(M \le 59\));

• Có \(30\%\) số test tương ứng \(30\%\) số điểm với \(N \le 10^{18}\).

Output

In ra một số nguyên duy nhất là số lượng số thập phân khác nhau từ \(1\) tới \(N\) mà khi biểu diễn ở hệ nhị phân có đúng \(K\) chữ số \(0\) có nghĩa.

Example

Input:

10 2

Output:

3

Note

Từ \(1\) tới \(10\) có các số nhị phân: \(1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010\). Có \(3\) số nhị phân có \(2\) chữ số \(0\) có nghĩa là: \(100\), \(1001\), \(1010\).