이진 크리스탈

이진 크리스탈은 이진수 표현에서 같은 숫자가 연속해서 나오는 횟수가 K 이하인 양의 정수이다. 예를 들어 K=2일 때, 5는 이진수로 101이므로 같은 숫자가 최대 1번 연속이어서 이진 크리스탈이다. 반면 7은 이진수로 111이므로 1이 3번 연속이어서 K=2일 때 이진 크리스탈이 아니다.

정수 N과 K가 주어졌을 때, 1 이상 N 이하의 정수 중 이진 크리스탈의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. (1 <= N <= 10^18, 1 <= K <= 60)

출력

1 이상 N 이하의 이진 크리스탈의 개수를 출력한다.

입출력 예시

입력 1

7 2

출력 1

6

입력 2

15 1

출력 2

4