Giải bài trực tuyến

Cho số nguyên không âm N (N < 2³¹). Hãy xác định xem trong phạm vi từ 0 tới N có bao nhiêu số mà trong dạng biểu diễn nhị phân của nó có đúng K chữ số 0 có nghĩa.

Ví dụ: N = 18, K = 3 có 3 số:

1. 8 = 1000

2. 17 = 10001

3. 18 = 10010

Input

Gồm một số dòng, mỗi chứa hai số nguyên N và K cách nhau một dấu cách.

Output

Ứng với mỗi bộ N, K ở Input đưa ra số lượng tìm được.

Example

Input:
18 3
8 1

Output:
3
4