这是这个问题的困难版本。唯一的区别是,在这个版本中,你需要输出鲍勃获胜的游戏选择数量,其中每堆石子的数量不固定。您必须解决这两个版本才能进行破解。
Alice 和 Bob 正在玩一个熟悉的游戏,他们轮流从 $$$n$$$ 堆中取出石头。最初,第 $$$i$$$ 堆中有 $$$x_i$$$ 石头,并且它具有关联值 $$$a_i$$$。当且仅当满足以下两个条件时,玩家才可以从第 $$$i$$$ 堆中拿走 $$$d$$$ 石子:
- $$$1 \le d \le a_i$$$,以及
- $$$x \, \& \, d = d$$$,其中 $$$x$$$ 是第 $$$i$$$ 堆中当前石子的数量,$$$\&$$$ 表示按位 AND 运算。
无法移动的玩家失败,爱丽丝先走。
您已获得每堆的 $$$a_i$$$ 值,但第 $$$i$$$ 堆中的石子数量尚未确定。对于第 $$$i$$$ 堆,$$$x_i$$$ 可以是 $$$1$$$ 和 $$$b_i$$$(含)之间的任何整数。也就是说,您可以选择一个数组 $$$x_1, x_2, \ldots, x_n$$$,使得所有桩都满足条件 $$$1 \le x_i \le b_i$$$。
您的任务是计算如果两名玩家都发挥最佳状态,Bob 获胜的游戏数量。如果任意一堆中的石子数量不同,即 $$$x$$$ 数组至少在一个位置不同,则认为两个游戏不同。
由于答案可能非常大,请输出对 $$$10^9 + 7$$$ 取模的结果。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的第一行包含 $$$n$$$ ($$$1 \le n \le 10^4$$$) — 堆的数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i < 2^{30}$$$)。
每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i < 2^{30}$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^4$$$。
输出
输出一个整数,即 Bob 获胜的游戏次数,以 $$$10^9 + 7$$$ 为模。
示例
输入 #1
7 3 1 2 3 3 2 2 1 13 45 5 5 4 7 8 6 4 4 5 5 5 4 6 4 8 8 12 13 14 12 3 92856133 46637598 12345678 29384774 73775896 87654321 2 65 12 110 31 4 677810235 275091182 428565855 720629731 74522416 889934149 3394714 230851724
输出 #1
4 4 0 6552 722019507 541 665443265
注意
在第一个测试用例中,无论我们选择 $$$x_2$$$ 和 $$$x_3$$$ 的哪个值,第二堆和第三堆总是会被选择一次,然后就不能再从中取出任何石头了。如果$$$x_1 = 2$$$,则无法从中取出任何棋子,因此鲍勃将进行最后一步。如果 $$$x_1 = 1$$$ 或 $$$x_1 = 3$$$,则可以在该堆上进行一次移动,因此 Alice 将进行最后一步。因此,当 $$$x = [2, 1, 1]$$$ 或 $$$x = [2, 1, 2]$$$ 或 $$$x = [2, 2, 1]$$$ 或 $$$x = [2, 2, 2]$$$ 时,Bob 获胜。
在第二个测试用例中,当 $$$x_1 = 14$$$ 或 $$$x_1 = 30$$$ 时,Bob 通过移除 $$$14 - k$$$ 石子获胜,其中 $$$k$$$ 是 Alice 在回合中移除的石子数量。当 $$$x_1 = 16$$$ 或 $$$x_1 = 32$$$ 时,鲍勃也会获胜,因为爱丽丝一开始就没有任何动作。