问题1230--三阳开泰

1230: 三阳开泰

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

题目描述

给定四个整数A,B,C,X
求三个非负整数组成的有序三元组(a,b,c)的个数,同时满足以下两个条件
1.a<=A并且b<=B并且c<=C
2.a,b,c三个数两两之间的异或和均不大于X
由于三元组的个数可能很大,你只需要输出结果mod(1e9+7)即可

输入

第一行为一个整数T(T<=100),表示数据组数
接下来T行,每行4个整数,A,B,C,X均小于等于1e18

输出

T行,每行1个整数,表示三元组的个数mod(1e9+7)

样例输入 Copy

1
3 5 2 4

样例输出 Copy

50