bits числа n (без ведущих нулей) и целое число steps.
С натуральным числом x можно сделать шаг: заменить его на количество единиц в его двоичной записи. Например, 13 = 1101₂ превращается в 3, а 3 = 11₂ — в 2.
Число x **сжимается**, если не более чем за steps шагов оно превращается в 1 (само число 1 сжимается за ноль шагов).
Посчитайте, сколько натуральных чисел, меньших n, сжимаются. Ответ может быть огромным — верните его по модулю 10⁹ + 7.
Обратите внимание: в bits бывает до 800 знаков, перебрать все числа не получится.bits="110", steps=1 → 3
Граница — 6. За один шаг до 1 доходят числа ровно с одним единичным битом: 1, 2 и 4.
bits="1010", steps=2 → 8
Граница — 10. Подходят числа с одним единичным битом (1, 2, 4, 8) и с двумя (3, 5, 6, 9): после первого шага получается 2, после второго — 1. Число 7 даёт 3 → 2 → 1 — это уже три шага.
bits="10", steps=5 → 1
Граница — 2, меньше неё только число 1, и оно уже равно 1.
bits состоит из 0 и 1 и начинается с 1bits="110", steps=1
3
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 40 тестов на сервере, включая скрытые.