utils/scrapers/prescraped/codeforces/Problems/1982E

Let $$$bit(x)$$$ denote the number of ones in the binary representation of a non-negative integer $$$x$$$.A subarray of an array is called $$$k$$$-good if it consists only of numbers with no more than $$$k$$$ ones in their binary representation, i.e., a subarray $$$(l, r)$$$ of array $$$a$$$ is good if for any $$$i$$$ such that $$$l \le i \le r$$$ condition $$$bit(a_{i}) \le k$$$ is satisfied.You are given an array $$$a$$$ of length $$$n$$$, consisting of consecutive non-negative integers starting from $$$0$$$, i.e., $$$a_{i} = i$$$ for $$$0 \le i \le n - 1$$$ (in $$$0$$$-based indexing). You need to count the number of $$$k$$$-good subarrays in this array.As the answer can be very large, output it modulo $$$10^{9} + 7$$$.