Задано натуральное десятичное число N (N ≤ 10⁹). Написать программу вычисления количества принадлежащих диапазону от 1 до N чисел, в двоичном представлении которых содержится ровно K значащих нулей. Например, для N = 18 и K = 3 таких чисел - 3 (8, 17, 18).

Ввод чисел N и K осуществляется с клавиатуры, полученный результат выводится на экран. Корректность входных данных проверять не требуется.

Максимальная оценка за задачу - 30 баллов.