Комивояжёр проводит много времени в пути, поэтому часто скучает. Чтобы скоротать время, он любит производить операции с числами. Одна из таких операций заключается в том, что он берёт натуральное число 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 один единичный бит) после применения ещё одной операции.
