Jee, You See?
Contest: Codeforces Round 788 (Div. 2)
Difficulty rating: 2400
Tags: bitmasks, combinatorics, dp

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
3 1 5 1

Example output:
13

Example input:
4 1 3 2

Example output:
4

Editorial:
Let's put aside the XOR constraint and only focus on the sum constraint.
let $$$G(X)$$$ be the number of ways to construct $$$n$$$ integers such that their sum is at most $$$X$$$.
We will construct each bit of the $$$n$$$ integers at the same time, we want to guarantee that the contribution of the sum of the bits generated at each position plus the sum of the previous bits wont exceed $$$X$$$ we only have to know the difference between the previous bits of $$$X$$$ (add 1 if the current bit is on) and the sum of the generated bits.
However we know for sure that at each position we can generate at most $$$n$$$ bits which will sum to $$$n$$$ at most, so for the next position the difference will be the $$$2$$$ * (current difference - the sum of the bits at the cur position). we can see that if the current difference has a value $$$\geq$$$ $$$2n$$$ we can place any number of bits at the remaining positions.
Let's define $$$dp[m][k]$$$ as the number of ways to construct the first $$$m$$$ bits of the $$$n$$$ integers such that their sum doesn't exceed $$$X$$$, where $$$k$$$ is min between (the difference between the previous bits and $$$X$$$) and $$$2n$$$.
We can have $$$count$$$ from 0 to $$$min(k,n)$$$ ones placed at the current bit and for each $$$count$$$ we have $$$n \choose count$$$ ways to distribute them.
Formally $$$dp[m][k]= \sum_{count=0}^{\min(n,k)} {n \choose count}\cdot dp[m+1][2(k-count+currentBit)]$$$ where $$$currentBit$$$ is one if the limit have the bit $$$m$$$ on.

For the XOR constraint we only have to make sure that count is even if the current bit of Z is 0 or odd if the current bit is 1.
The answer of the problem will be $$$G(R)-G(L-1)$$$.