Обозначим за \(bit(x)\) количество единичных бит в двоичной записи неотрицательного целого числа \(x\).
Назовем подотрезок массива \(k\)-хорошим, если он состоит только из чисел, в которых не более \(k\) единичных бит, то есть подотрезок \((l, r)\) массива \(a\) хороший, если для любого \(i\), такого, что \(l \le i \le r\) выполняется \(bit(a_{i}) \le k\).
У вас есть массив \(a\) длины \(n\), состоящий из последовательных неотрицательных целых чисел начиная с \(0\), то есть \(a_{i} = i\) для \(0 \le i \le n - 1\) (в \(0\)-индексации). Вам необходимо посчитать количество \(k\)-хороших подотрезков в этом массиве.
Поскольку ответ может быть очень большим, выведите его по модулю \(10^{9} + 7\).
Примечание
Для первого набора входных данных \(a = [0, 1, 2, 3, 4, 5]\), \(k = 1\).
Чтобы найти ответ, давайте запишем все числа в двоичной записи:
\(\)a = [\color{green}{000}, \color{green}{001}, \color{green}{010}, \color{red}{011}, \color{green}{100}, \color{red}{101}]\(\)
Отсюда видно, что числа \(3\) и \(5\) имеют \(2 \ge (k = 1)\) единичных бита в двоичной записи, поэтому в ответ должны войти все подотрезки, в которых нет ни \(3\), ни \(5\), это отрезки (в \(0\)-индексации): (\(0\), \(0\)), (\(0\), \(1\)), (\(0\), \(2\)), (\(1\), \(1\)), (\(1\), \(2\)), (\(2\), \(2\)), (\(4\), \(4\)).