牛牛和牛可乐是一对好朋友，现在牛牛从值域[l1,r1]中随机给出一个数字a，牛可乐从值域[l2,r2]中随机给出一个数字b。问你a b的数学期望。其中为位运算符，表示按位取异或。 为了避免你输出的答案出现精度误差，请你输出一个分数 ，其中表示在mod 条件下的乘法逆元。数据保证，也就是说保证在该模条件下有意义,并且保证不是mod的倍数。
输入描述:
第一行是一个正整数T()表示有T组案例。接下来T行，每行四个正整数（）。


输出描述:
请输出期望
示例1

输入

2
3 5 7 8
1 3 3 5

输出

500000011
222222228

说明

a可取3,4,5，b可取7,8
3\oplus7=4，4\oplus7=3，5\oplus7=2
3\oplus8=11，4\oplus8=12，5\oplus8=13
共6种情况，答案为(4+3+2+11+12+13)/6=45/6=15/2=15*2^{-1}(mod \,\,\, 10^9+7)=15*500000004%mod=500000011

备注:
乘法逆元：
加载中...