CF1982E Number of k-good subarrays

设 $bit(x)$ 表示非负整数 $x$ 的二进制表示中 $1$ 的个数。 一个数组的子数组被称为 $k$-好子数组，如果它只包含二进制表示中 $1$ 的个数不超过 $k$ 的数。也就是说，数组 $a$ 的子数组 $(l, r)$ 是 $k$-好子数组，当且仅当对于任意 $l \le i \le r$，都有 $bit(a_i) \le k$。 给定一个长度为 $n$ 的数组 $a$，其元素为从 $0$ 开始的连续非负整数，即 $a_i = i$，其中 $0 \le i \le n - 1$（下标从 $0$ 开始）。你需要计算该数组中 $k$-好子数组的数量。 由于答案可能非常大，请输出对 $10^9 + 7$ 取模后的结果。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来的每组测试用例包含一行，包含两个整数 $n$、$k$（$1 \le n \le 10^{18},\ 1 \le k \le 60$）。

对于每组测试用例，输出一个整数，表示 $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$ 的二进制中 $1$ 的个数为 $2 \ge (k = 1)$，所以答案应包括所有不包含 $3$ 或 $5$ 的子数组，即（下标从 $0$ 开始）：$(0, 0)$，$(0, 1)$，$(0, 2)$，$(1, 1)$，$(1, 2)$，$(2, 2)$，$(4, 4)$。 由 ChatGPT 4.1 翻译