题目内容

给定正整数 $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$ 。