Description:
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$$$.
Input Format:
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}$$$).
Output Format:
Print the number of arrays $$$a$$$ satisfying all requirements modulo $$$10^9+7$$$.
Note:
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]$$$.