#P16899. [Ontak2026]位运算技巧

[Ontak2026]位运算技巧

题目描述

给定整数区间 [a,b][a,b]。

求有多少个不同的无序整数对 (x,y)(x,y) 满足:

  • x,y∈[a,b]x,y\in[a,b];
  • x∣y=x+yx\mathbin{|}y=x+y,其中 ∣| 表示按位或(bitwise OR)。

只交换两个数次序得到的两个数对视为同一个数对。

输入格式

第一行包含测试数据组数 ZZ:

1≤Z≤10001\le Z\le1000。

接下来 ZZ 行,每行包含两个整数 a,ba,b:

1≤a<b≤10181\le a<b\le10^{18}。

输出格式

对于每组数据,输出满足条件的无序数对数量对 109+710^9+7 取模后的结果。

样例

2
1 8
8 20
13
22

样例说明

第一组数据中的 1313 个数对为:

$(1,2),(1,4),(1,6),(1,8),(2,4),(2,5),(2,8),(3,4),(3,8),(4,8),(5,8),(6,8),(7,8)$。

例如 6∣8=14=6+86\mathbin{|}8=14=6+8。

子任务

子任务 限制 分值
1 a,b≤106a,b\le10^6,b−a≤100b-a\le100,Z≤100Z\le100 12
2 b−a≤10000b-a\le10000,Z=50Z=50 41
3 无额外限制 47