Cho số nguyên không âm ~N (N < 2^{31})~. 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 dòng 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.

Sample Input

18 3
8 1

Sample Output

3
4