解题思路

关键观察

题目要求统计有序对 $(a,b)$（$1\le a,b\le n$）且满足 $(a|b)\le K$。 注意这是“数值上的 $\le$”，而不是“按位包含关系”。例如：$K=5\,(0101_2)$，$(a|b)=3\,(0011_2)$ 也满足 $\le K$（虽然 3 在某些位上为 1 而 $K$ 为 0）。

因此，不能简单地只数“只用到了 $K$ 的 1 位的数”。更稳妥的做法是二进制数位 DP（Digit DP）：

我们从最高位到最低位逐位决定 $(a_i,b_i)\in\{0,1\}\times\{0,1\}$，同时维持三种“前缀是否紧贴上界”的状态：

题目内容

给定正整数 $n$ 和整数 $K$ ，考虑所有有序整数对 $(a,b)$ ，满足 $1≤a,b≤n$ 且 $(a丨b)≤K$ ，其中 $a丨b$ 表示 $a$ 和 $b$ 的按位或。

请计算满足条件的数对总数。由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。

名词解释：按位或：两个二进制数对应位执行逻辑或运算，记作 $x丨y$ ，例如 $5丨3=7$ 。

输入描述

第一行输入整数 $t(1≤t≤10^4)$ ，表示数据组数。 接下来 $t$ 行，每行输入两个整数 $n,K(1≤n≤10^{18},0≤K≤10^{18})$ 。

输出描述

对于每组测试数据，输出一行整数，表示满足条件的有序数对个数。由于答案可能很大，请将结果对 $(10^9+7)$ 取模后输出。

样例1

输入

3
5 3
5 1
10 5

输出

9
1
17

说明

在这个样例中：

当 $n=5,K =3$ 时，$(a,b)$ 满足条件的有 $a,b∈${$1,2,3$},共 $3×3=9$ 对;

当 $n=6,K=1$ 时,只有 $(1,1)$ 满足，结果为 $1$ 。