让 $$$bit(x)$$$ 表示非负整数 $$$x$$$ 的二进制表示形式中 1 的数量。
数组的子数组称为 $$$k$$$-好,如果它仅由二进制表示中不超过 $$$k$$$ 的数字组成,即数组 $$$a$$$ 的子数组 $$$(l, r)$$$ 是好的,如果对于任何 $$$i$$$ 满足 $$$l \le i \le r$$$ 条件$$$bit(a_{i}) \le k$$$ 满足。
给定一个长度为 $$$n$$$ 的数组 $$$a$$$,由从 $$$0$$$ 开始的连续非负整数组成,即 $$$a_{i} = i$$$ 表示 $$$0 \le i \le n - 1$$$(基于 $$$0$$$ 的索引)。您需要计算该数组中 $$$k$$$-good 子数组的数量。
由于答案可能非常大,因此输出它对 $$$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$$$ 为模。
示例
输入 #1
10 6 1 16 2 1 1 3 1 31 3 14 1 1337 5 100000 20 795569939321040850 56 576460752303423268 59
输出 #1
7 35 1 6 155 8 7323 49965 741136395 66679884
注意
对于第一个测试用例 $$$a = [0, 1, 2, 3, 4, 5]$$$,$$$k = 1$$$。
为了找到答案,我们将所有数字写成二进制表示形式:
$$$$$$a = [\颜色{绿色}{000}、\颜色{绿色}{001}、\颜色{绿色}{010}、\颜色{红色}{011}、\颜色{绿色}{100}、\颜色{红色}{101}]$$$$$$
由此可见,数字 $$$3$$$ 和 $$$5$$$ 在其二进制表示中具有 $$$2 \ge (k = 1)$$$ 个,因此答案应包括所有不包含 $$$3$$$ 或 $$$5$$$ 的子数组,这些子数组是子数组(基于 $$$0$$$ 的索引): ($$$0$$$, $$$0$$$), ($$$0$$$, $$$1$$$), ($$$0$$$, $$$2$$$), ($$$1$$$, $$$1$$$), ($$$1$$$, $$$2$$$), ($$$2$$$, $$$2$$$), ($$$4$$$, $$$4$$$)。