CF1670F.Jee, You See?

During their training for the ICPC competitions, team "Jee You See" stumbled upon a very basic counting problem. After many "Wrong answer" verdicts, they finally decided to give up and destroy turn-off the PC. Now they want your help in up-solving the problem.

You are given 4 integers $n$, $l$, $r$, and $z$. Count the number of arrays $a$ of length $n$ containing non-negative integers such that:

• $l\le a_1+a_2+\ldots+a_n\le r$, and
• $a_1\oplus a_2 \oplus \ldots\oplus a_n=z$, where $\oplus$ denotes the bitwise XOR operation.

Since the answer can be large, print it modulo $10^9+7$.

在 ICPC 竞赛训练过程中，队伍“Jee You See”偶然遇到了一个非常基础的计数问题。在多次提交得到“答案错误（Wrong answer）”判定后，他们最终决定放弃并关掉电脑。现在他们希望你能帮忙补题（up-solving）解决该问题。

给定四个整数 $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$ 表示按位异或（bitwise XOR） 运算。

由于答案可能很大，请将结果对 $10^9+7$ 取模后输出。

The only line contains four integers $n$, $l$, $r$, $z$ ($1 \le n \le 1000$, $1\le l\le r\le 10^{18}$, $1\le z\le 10^{18}$).

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

Print the number of arrays $a$ satisfying all requirements modulo $10^9+7$.

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

The following arrays satisfy the conditions for the first sample:

• $[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]$.

The following arrays satisfy the conditions for the second sample:

• $[2, 0, 0, 0]$;
• $[0, 2, 0, 0]$;
• $[0, 0, 2, 0]$;
• $[0, 0, 0, 2]$.

以下数组满足第一个样例的条件：

• $[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]$。