CF1670F Jee, You See?

在为 ICPC 比赛训练时，队伍 "Jee You See" 遇到了一个非常基础的计数问题。在经历了多次“Wrong answer”后，他们最终决定放弃并关掉电脑。现在他们希望你能帮忙解决这个问题。 给定四个整数 $n$、$l$、$r$ 和 $z$，请计算长度为 $n$ 的非负整数数组 $a$ 的个数，满足： - $l \le a_1 + a_2 + \ldots + a_n \le r$； - $a_1 \oplus a_2 \oplus \ldots \oplus a_n = z$，其中 $\oplus$ 表示[按位异或](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)操作。 由于答案可能很大，请输出答案对 $10^9+7$ 取模后的结果。

一行包含四个整数 $n$、$l$、$r$、$z$（$1 \le n \le 1000$，$1 \le l \le r \le 10^{18}$，$1 \le z \le 10^{18}$）。

输出满足所有要求的数组 $a$ 的个数，对 $10^9+7$ 取模。

对于第一个样例，满足条件的数组有： - $[1, 0, 0]$； - $[0, 1, 0]$； - $[3, 2, 0]$； - $[2, 3, 0]$； - $[0, 0, 1]$； - $[1, 1, 1]$； - $[2, 2, 1]$； - $[3, 0, 2]$； - $[2, 1, 2]$； - $[1, 2, 2]$； - $[0, 3, 2]$； - $[2, 0, 3]$； - $[0, 2, 3]$。 对于第二个样例，满足条件的数组有： - $[2, 0, 0, 0]$； - $[0, 2, 0, 0]$； - $[0, 0, 2, 0]$； - $[0, 0, 0, 2]$。 由 ChatGPT 4.1 翻译