CF2027E2 Bit Game (Hard Version)

这是该问题的困难版本。唯一的区别在于，在本版本中你需要输出 Bob 获胜的游戏方案数，其中每堆石子的数量并不是固定的。你必须同时解决两个版本才能进行 hack。 Alice 和 Bob 正在玩一个熟悉的游戏，他们轮流从 $n$ 堆石子中取石子。最初，第 $i$ 堆有 $x_i$ 个石子，并且该堆有一个对应的值 $a_i$。一名玩家可以从第 $i$ 堆中取走 $d$ 个石子，当且仅当满足以下两个条件： - $1 \le d \le a_i$，且 - $x \,\&\, d = d$，其中 $x$ 是当前第 $i$ 堆的石子数，$\&$ 表示[按位与运算](https://en.wikipedia.org/wiki/Bitwise_operation#AND)。 无法进行操作的玩家判负，Alice 先手。 你已知每堆的 $a_i$，但每堆的石子数 $x_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$ 取模。

在第一个测试用例中，无论 $x_2$ 和 $x_3$ 取什么值，第二堆和第三堆都只能被操作一次，然后就无法再取石子了。如果 $x_1 = 2$，那么无法从该堆取石子，因此最后一步由 Bob 完成。如果 $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$ 时，Alice 一开始就无法进行操作，因此 Bob 获胜。 由 ChatGPT 4.1 翻译