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

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