C. Комивояжёр и специальные числа
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Комивояжёр проводит много времени в пути, поэтому часто скучает. Чтобы скоротать время, он любит производить операции с числами. Одна из таких операций заключается в том, что он берёт натуральное число x и уменьшает его до количества бит, которые установлены в 1 в двоичной записи числа x. Например, для числа 13 верно, что 1310 = 11012, значит, в нём есть 3 единичных бита, поэтому за одну операцию 13 уменьшится до 3.

Он называет число специальным если минимальное количество операций, требуемых для уменьшения этого числа до 1 равно k.

Комивояжёру интересно, сколько существует специальных чисел, не превосходящих n. Помогите ему.

Так как ответ может быть большим, выведите его по модулю 109 + 7.

Входные данные

В первой строке содержится целое число n (1 ≤ n < 21000).

Во второй строке содержится целое число k (0 ≤ k ≤ 1000).

Учтите, что n задано в двоичной системе счисления без ведущих нулей.

Выходные данные

Выведите одно целое число — количество специальных чисел, не превосходящих n, по модулю 109 + 7.

Примеры
Входные данные
110
2
Выходные данные
3
Входные данные
111111011
2
Выходные данные
169
Примечание

В первом тестовом примере тремя специальными числами являются 3, 5 и 6. За одну операцию они уменьшаются до 2 (потому что в каждом из чисел 3, 5 и 6 два единичных бита), а затем до 1 (потому что в числе 2 один единичный бит) после применения ещё одной операции.