Комивояжёр проводит много времени в пути, поэтому часто скучает. Чтобы скоротать время, он любит производить операции с числами. Одна из таких операций заключается в том, что он берёт натуральное число x и уменьшает его до количества бит, которые установлены в 1 в двоичной записи числа x. Например, для числа 13 верно, что 1310 = 11012, значит, в нём есть 3 единичных бита, поэтому за одну операцию 13 уменьшится до 3.
Он называет число специальным если минимальное количество операций, требуемых для уменьшения этого числа до 1 равно k.
Комивояжёру интересно, сколько существует специальных чисел, не превосходящих n. Помогите ему.
Так как ответ может быть большим, выведите его по модулю 109 + 7.
Примечание
В первом тестовом примере тремя специальными числами являются 3, 5 и 6. За одну операцию они уменьшаются до 2 (потому что в каждом из чисел 3, 5 и 6 два единичных бита), а затем до 1 (потому что в числе 2 один единичный бит) после применения ещё одной операции.