Jee, You See?

2000ms

262144K

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:

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:

Print the number of arrays $$$a$$$ satisfying all requirements modulo $$$10^9+7$$$.

Sample Input:

3 1 5 1

Sample Output:

Sample Input:

4 1 3 2

Sample Output:

Sample Input:

2 1 100000 15629

Sample Output:

Sample Input:

100 56 89 66

Sample Output:

981727503

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

Informação

Provedor Codeforces

Código CF1670F