Jee, You See?

题意翻译

给定 4 个整数 $n,l,r,z$ ($1 \le n \le 1000,1 \le l \le r \le 10^{18},1 \le z \le 10^{18}$ 求满足一下条件的序列 $a$ 的个数： 1. $a_i$ 为非负整数 2. $l \le a_1 + a_2 + \dots a_n \le r $ 3. $a_1 \oplus a_2 \oplus \dots \oplus a_n = z$ 其中 $\oplus$ 表示二进制按位异或运算 答案对 $10^9 + 7$ 取模

题目描述

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](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) operation. Since the answer can be large, print it modulo $ 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} $ ).

输出格式

Print the number of arrays $ a $ satisfying all requirements modulo $ 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

说明

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