牛牛的随机数

题号：NC201776
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛牛和牛可乐是一对好朋友，现在牛牛从值域[l1,r1]中随机给出一个数字a，牛可乐从值域[l2,r2]中随机给出一个数字b。问你a $\oplus$ b的数学期望。其中 $\oplus$ 为位运算符，表示按位取异或。

为了避免你输出的答案出现精度误差，请你输出一个分数 $P*Q^{-1}(mod\,\, 10^9+7)$ ，其中 $Q^{-1}$ 表示在mod 条件下的乘法逆元。数据保证 $gcd(Q,10^9+7)=1$ ，也就是说保证 $Q^{-1}$ 在该模条件下有意义,并且保证 $(r_1-l_1+1)(r_2-l_2+1)$ 不是mod的倍数。

输入描述:

第一行是一个正整数T( $1 \leq T \leq 10^5$ )表示有T组案例。

接下来T行，每行四个正整数 $l_1,r_1,l_2,r_2$ （ $1 \leq l_1 \leq r_1 \leq 10^{18},1 \leq l_2 \leq r_2 \leq 10^{18}$ ）。

输出描述:

请输出期望

示例1

输入

复制

2
3 5 7 8
1 3 3 5

输出

复制

500000011
222222228

说明

a可取3,4,5，b可取7,8
37=4，47=3，57=2
38=11，48=12，58=13
共6种情况，答案为(4+3+2+11+12+13)/6=45/6=15/2==15*500000004%mod=500000011

备注:

乘法逆元：