Задано натуральное десятичное число N (N<=1 000 000
000).
Требуется написать программу вычисления количества принадлежащих
диапазону от 1 до N
чисел, в двоичном представлении которых содержится ровно K значащих нулей. Например, для N=18 и K=3 таких чисел — 3 (8, 17, 18).
Технические
требования:
Ограничение по
времени тестирования: 1 секунда на один тест.
Формат
входных данных:
Во входном файле
в первой строке записано число N, а во второй - K.
Формат
выходных данных:
Вывести в выходной
файл полученное количество.
Пример
входных и выходных данных:
