← 返回题目列表

Codeforces · 1670/F

F. 天啊,你看到了吗?

中文机器翻译题面 查看原题

在ICPC比赛训练期间,“Jee You See”团队偶然发现了一个非常基本的计数问题。经过多次“答案错误”的判决后,他们最终决定放弃并销毁关闭电脑。现在他们需要你的帮助来解决这个问题。

给你 4 个整数 $$$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$$$ 表示按位异或运算。

由于答案可能很大,请打印 $$$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

3 1 5 1

输出 #1

13

输入 #2

4 1 3 2

输出 #2

4

输入 #3

2 1 100000 15629

输出 #3

49152

输入#4

100 56 89 66

输出#4

981727503

注意

以下数组满足第一个样本的条件:

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